Spojnicový graf hypergrafu

Spojnicový graf hypergrafu  je graf , jehož množina vrcholů je množina hyperedge hypergraphu a dvě hyperhrany sousedí, pokud mají neprázdný průsečík. Jinými slovy, spojnicový graf hypergrafu je průsečíkový graf rodiny konečných množin. Koncept je zobecněním spojnicového grafu běžného grafu.

Otázky týkající se spojnicových grafů hypergrafů jsou často zobecněním otázek týkajících se spojnicových grafů běžných grafů. Například hypergraf, jehož všechny hrany mají velikost k , se nazývá k-uniform' (2-stejnoměrný hypergraf je obyčejný graf). V teorii hypergrafů je často přirozené vyžadovat k - jednotnost. Každý obyčejný graf je spojnicovým grafem nějakého hypergrafu, ale pokud zafixujeme velikost hrany k (počet bodů v množině patřících hraně), ne každý graf je spojnicovým grafem nějakého k - jednotného grafu. Hlavním úkolem je popsat spojnicové grafy pro každý .

Hypergraf se nazývá lineární , pokud má jakákoliv dvojice hyperhran v průsečíku nejvýše jeden vrchol. Libovolný graf je spojnicovým grafem nejen nějakého hypergrafu, ale i nějakého lineárního hypergrafu [1] .

Spojnicové grafy k -jednotných hypergrafů,

Beinecke [2] popsal spojnicové grafy regulárních grafů uvedením 9 zakázaných indukovaných podgrafů (viz záznam o spojnicových grafech ). Pro čárové grafy k-uniformních hypergrafů pro žádné není znám žádný popis zakázanými indukovanými podgrafy a Lovas [3] ukázal, že takový popis ve formě konečného seznamu pro k = 3 neexistuje.

Kraus [4] popsal spojnicové grafy běžných grafů z hlediska pokrytí kliky ( Viz Spojnicový graf ). Globální popis typu Kraus pro spojnicové grafy k -uniformních hypergrafů pro libovolné uvádí Berge [1] .

Spojnicové grafy k -jednotných spojnicových hypergrafů pro

Globální popis typu Kraus pro spojnicové grafy k -uniformních spojnicových hypergrafů pro libovolný je uveden autory Naik, Rao, Srikhande a Singhi [5] . Zároveň našli konečný počet zakázaných indukovaných podgrafů pro lineární 3-uniformní hypergrafy s minimálním vrcholovým stupněm alespoň 69. Metelsky a Tyshkevich [6] a Jakobson, Kezdi, Lekhel [7] zlepšili tuto hranici na 19 , zatímco Skums, Suzdal a Tyszkiewicz [8] toto snížili na 16. Metelsky a Tyszkiewicz [6] také dokázali, že pro k > 3 takový seznam pro lineární k -uniformní hypergrafy neexistuje, bez ohledu na to, jaká míra omezení je zavedena.

Složitost hledání popisu lineárních k -uniformních hypergrafů spočívá v tom, že existuje nekonečně mnoho zakázaných generovaných podgrafů. Abychom uvedli příklad, pro m > 0 vezměte řetězec m diamantových grafů tak, aby diamanty sdílely vrcholy druhého řádu, a přidejte některé převislé vrcholy, jak je znázorněno na obrázku, abyste získali jednu z rodin minimálních zakázaných podgrafů [5 ] [9] .

Existuje řada zajímavých popisů pro spojnicové grafy lineárních k -uniformních hypergrafů podaných různými autory [10] , s výhradou omezení minimálního stupně vrcholů nebo minimálního stupně hran. Minimální okrajový stupeň pro popis liniových grafů k -jednotných liniových hypergrafů pro libovolný , který není menší v díle Naika, Rao, Srikhande a Sighi [5] , je redukován na v dílech Jakobsona, Kezdiho, Lehela [7 ] a Zverovič [11] .

Složitost rozpoznávání spojnicových grafů lineárních k -uniformních hypergrafů bez omezení minimálního stupně (nebo minimálního stupně hran) není známa. Pro k = 3 a minimální stupeň alespoň 19 je rozpoznání možné v polynomiálním čase [7] [6] ). Skums, Suzdal a Tyszkiewicz [8] snížili minimální stupeň na 10.

V pracích Nike et al., Jacobson et al., Metelsky et al. a Zverovich je mnoho nevyřešených problémů a hypotéz.

Poznámky

  1. ↑ 12 Berge , 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 a 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 a Tyshkevich, 1997 ; Zverovič, 2004
  11. ↑ Zverovič, 2004 .

Literatura