Hipergráf vonalgráfja

A hipergráf vonalgráfja  olyan gráf , amelynek csúcskészlete a hipergráf hiperélhalmaza, és két hiperél szomszédos, ha nem üres metszéspontjuk van. Más szóval, a hipergráf vonalgráfja véges halmazok családjának metszésgráfja. A fogalom egy közönséges gráf vonalgráfjának általánosítása .

A hipergráfok vonaldiagramjaira vonatkozó kérdések gyakran a közönséges gráfok vonalgráfjaira vonatkozó kérdések általánosításai. Például egy olyan hipergráfot, amelynek minden éle k méretű , k -uniformnak nevezzük (a 2-uniformú hipergráf egy közönséges gráf). A hipergráf-elméletben gyakran természetes a k -uniformitás megkövetelése. Bármely közönséges gráf valamilyen hipergráf vonalgráfja, de ha rögzítjük a k élméretet (az élhez tartozó halmaz pontjainak számát), akkor nem minden gráf egy k - egyenletes gráf vonalgráfja. A fő feladat vonalgrafikonok leírása mindegyikhez .

A hipergráfot lineárisnak nevezzük , ha bármely hiperélpárnak legfeljebb egy csúcsa van a metszéspontban. Bármely gráf nem csak valamilyen hipergráf vonalgráfja, hanem valamilyen lineáris hipergráfnak is [1] .

K -uniform hipergráfok vonalgráfjai ,

Beinecke [2] a szabályos gráfok vonalgráfjait 9 tiltott indukált részgráf felsorolásával írta le (lásd a vonalgráfok bejegyzését ) . Nem ismert a tiltott indukált részgráfok leírása a k-uniform hipergráfok vonalgráfjaira bármely -re , és Lovas [3] kimutatta, hogy nincs ilyen leírás véges lista formájában k = 3 esetén.

Kraus [4] a közönséges gráfok vonalgráfjait írta le a klikk lefedettség szempontjából ( Lásd Line graph ). A Kraus típus globális leírását bármely k -uniform hipergráf vonalgráfjaihoz Berge [1] adja meg .

K -uniform vonalhipergráfok vonalgráfjai a

Naik, Rao, Srikhande és Singhi [5] adta meg a Kraus típus globális leírását bármely k -uniform vonalhipergráf vonalgráfjaihoz . Ugyanakkor véges számú tiltott indukált részgráfot találtak lineáris 3-uniform hipergráfokhoz, legalább 69 csúcsfokozattal. Metelsky és Tyshkevich [6] , valamint Jakobson, Kezdi, Lekhel [7] ezt a korlátot 19-re javította. , míg Skums, Suzdal és Tyszkiewicz [8] ezt 16-ra csökkentette. Metelsky és Tyszkiewicz [6] azt is bebizonyította, hogy k > 3 esetén nincs ilyen lista a lineáris k -uniform hipergráfokhoz, függetlenül attól, hogy milyen fokos megszorítást alkalmaznak.

A lineáris k -uniform hipergráfok leírásának megtalálásának bonyolultsága az , hogy végtelenül sok tiltott generált részgráf létezik. Példaként m > 0 esetén vegyünk egy m gyémánt gráfból álló láncot úgy, hogy a gyémántok másodrendű csúcsaik legyenek, és adjunk hozzá néhány függő csúcsot, amint az az ábrán látható, hogy megkapjuk a minimálisan tiltott részgráfok egyik családját [5 ] [9] .

Számos érdekes leírás létezik a lineáris k -uniform hipergráfok vonalgráfjairól különböző szerzőktől [10] , a csúcsok minimális fokára vagy az élek minimális fokára vonatkozó korlátozásokkal. A k -uniform vonalhipergráfok vonalgráfjainak leírásához szükséges minimális élfokozat, amely Naik, Rao, Srikhande és Sighi [5] munkáiban nem kevesebb , Jakobson, Kezdi, Lehel munkáiban [7] ] és Zverovich [11] .

A lineáris k -uniform hipergráfok vonalgráfjainak felismerésének bonyolultsága a minimális fok (vagy az élek minimális foka) korlátozása nélkül nem ismert. K = 3 és legalább 19 minimális fok esetén a felismerés polinomiális időben lehetséges [ 7] [6] ). Skums, Suzdal és Tyszkiewicz [8] 10-re csökkentette a minimális fokozatot.

Sok megoldatlan probléma és hipotézis található Nike és munkatársai, Jacobson és munkatársai, Metelsky és mtsai, valamint Zverovich munkáiban.

Jegyzetek

  1. ↑ Berge 12. , 1989 .
  2. ↑ Beineke, 1968 .
  3. ↑ Lovász, 1977 .
  4. ↑ Krausz, 1943 .
  5. ↑ 1 2 3 Naik, Rao, Shrikhande, Singhi, 1980 .
  6. ↑ 1 2 3 Metelsky és Tyshkevich, 1997 .
  7. ↑ 1 2 3 Jacobson, Kézdy, Lehel, 1997 .
  8. ↑ 1 2 Skums, Suzdal', Tyshkevich, 2009 .
  9. ↑ Naik, Rao, Shrikhande, Singhi, 1982 .
  10. ↑ Naik, Rao, Shrikhande, Singhi, 1980 ; Naik, Rao, Shrikhande, Singhi 1982 ; Jacobson, Kézdy, Lehel, 1997 ; Metelsky és Tyshkevich, 1997 ; Zverovich, 2004
  11. ↑ Zverovich, 2004 .

Irodalom