Čárový graf hypergrafu - Line graph of a hypergraph - Wikipedia

v teorie grafů, zejména v teorii hypergrafy, spojnicový graf hypergrafu H, označeno L (H), je graf jehož vrcholová množina je množina hyperhranů H, se dvěma vrcholy sousedícími s L (H) když jejich odpovídající hyperedge mají neprázdnou křižovatku v H. Jinými slovy, L (H) je průsečíkový graf rodiny konečných množin. Jedná se o zobecnění hranový graf grafu.

Otázky o spojnicových grafech hypergrafů jsou často zevšeobecněním otázek o spojnicových grafech grafů. Například hypergraf, jehož okraje mají velikost k je nazýván k-jednotný. (2 uniformní hypergraf je graf). V teorii hypergrafů je často přirozené vyžadovat, aby hypergrafy byly k-jednotný. Každý graf je spojnicový graf nějakého hypergrafu, ale vzhledem k pevné velikosti okraje k, ne každý graf je u některých spojnicový k-jednotný hypergraf. Hlavním problémem je charakterizovat ty, které jsou pro každého k ≥ 3.

Hypergrafie je lineární pokud se každá dvojice hyperedges protíná nejvýše v jednom vrcholu. Každý graf je spojnicový graf, a to nejen nějakého hypergrafu, ale i nějakého lineárního hypergrafu (Berge 1989 ).

Čárové grafy k-jednotné hypergrafy, k ≥ 3

Beineke (1968) charakterizované spojnicové grafy grafů se seznamem 9 zakázané indukované podgrafy. (Viz článek na spojnicové grafy.) O čárových grafech k-uniformních hypergrafů pro žádnou není známa charakterizace zakázanými indukovanými podgrafy k ≥ 3 a Lovász (1977) ukázal, že neexistuje žádná taková charakterizace konečným seznamem, pokud k = 3.

Krausz (1943) charakterizované spojnicové grafy grafů z hlediska klika kryty. (Vidět Čárové grafy.) Globální charakterizace Krauszova typu pro spojnicové grafy k-jednotné hypergrafy pro všechny k ≥ 3 bylo dáno Berge (1989).

Čárové grafy k-jednotné lineární hypergrafy, k ≥ 3

Globální charakterizace Krauszova typu pro spojnicové grafy k-jednotné lineární hypergrafy pro všechny k ≥ 3 bylo dáno Naik a kol. (1980). Současně našli konečný seznam zakázaných indukovaných podgrafů pro lineární 3 uniformní hypergrafy s minimálním stupněm vrcholu nejméně 69. Metelsky & Tyshkevich (1997) a Jacobson, Kézdy a Lehel (1997) vylepšil tuto hranici na 19. Nakonec Skums, Suzdal '& Tyshkevich (2005) snížil tuto hranici na 16. Metelsky & Tyshkevich (1997) také prokázal, že pokud k > 3, pro lineární neexistuje žádný takový konečný seznam k-jednotné hypergrafy, bez ohledu na to, jaká dolní mez je umístěna na stupni.

Obtíž při hledání charakterizace lineárního k-jednotný hypergraf je způsoben tím, že existuje nekonečně mnoho zakázaných indukovaných podgrafů. Uvedu příklady, pro m > 0, zvažte řetězec m diamantové grafy tak, že následující diamanty sdílejí vrcholy stupně dva. Pro k ≥ 3, přidejte závěsné hrany na každém vrcholu stupně 2 nebo 4, abyste získali jednu z rodin minimálně zakázaných podgrafů Naik, Rao a Shrikhande et al. (1980, 1982 ), jak je znázorněno zde. To nevylučuje ani existenci polynomiálního rozpoznávání, ani možnost zakázané indukované charakterizace podgrafu podobnou liniovým grafům grafů od Beineke.

Opakovaný diamantový graf.svg

Pro lineární grafy lineárních je k dispozici několik zajímavých charakterizací k- jednotné hypergrafy způsobené různými autory (Naik, Rao & Shrikhande et al.1980, 1982, Jacobson, Kézdy a Lehel 1997, Metelsky & Tyshkevich 1997, a Zverovich 2004 ) za omezení minimálního stupně nebo minimálního stupně okraje G. Minimální stupeň okraje k3-2k2+1 palce Naik a kol. (1980) se sníží na 2k2-3k+1 palce Jacobson, Kézdy a Lehel (1997) a Zverovich (2004) charakterizovat spojnicové grafy k-jednotné lineární hypergrafy pro všechny k ≥ 3.

Složitost rozpoznávání lineárních grafů lineárního k-jednotné hypergrafy bez omezení minimálního stupně (nebo minimálního okrajového stupně) nejsou známy. Pro k = 3 a minimální stupeň alespoň 19, rozpoznávání je možné v polynomiálním čase (Jacobson, Kézdy a Lehel 1997 a Metelsky & Tyshkevich 1997 ). Skums, Suzdal '& Tyshkevich (2005) snížil minimální stupeň na 10.

Existuje mnoho zajímavých otevřených problémů a domněnek v Naik et al., Jacoboson et al., Metelsky et al. a Zverovich.

Graf disjunktnosti

The graf disjunktnosti hypergrafu H, označeno D (H), je graf, jehož množina vrcholů je množina hyperedges H, se dvěma vrcholy sousedícími s D (H), když jsou jejich odpovídající hyperedge disjunktní v H.[1] Jinými slovy, D (H) je doplňkový graf z L (H). A klika v D (H) odpovídá nezávislé množině v L (H) a naopak.

Reference

  1. ^ Meshulam, Roy (01.01.2001). "The Clique Complex and Hypergraph Matching". Combinatorica. 21 (1): 89–94. doi:10,1007 / s004930170006. ISSN  1439-6912. S2CID  207006642.
  • Heydemann, M. C .; Sotteau, D. (1976), „Čárové grafy hypergrafů II“, Kombinatorika (Proc. Fifth Hungarian Colloq., Keszthely, 1976)Colloq. Matematika. Soc. J. Bolyai, 18, str. 567–582, PAN  0519291.
  • Krausz, J. (1943), „Démonstration nouvelle d'une théorème de Whitney sur les réseaux“, Rohož. Fiz. Lapok, 50: 75–85, PAN  0018403. (V maďarštině, s francouzským abstraktem.)
  • Lovász, L. (1977), „Problém 9“, Beiträge zur Graphentheorie und deren Anwendungen, Vorgetragen auf dem Internationalen Kolloquium v ​​Oberhofu (DDR), s. 313.
  • Naik, Ranjan N .; Rao, S. B .; Shrikhande, S. S.; Singhi, N. M. (1980), „Průnikové grafy z k-jednotné hypergrafy ", Kombinatorická matematika, optimální designy a jejich aplikace (Proc. Sympos. Combin. Math. And Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978), Annals of Discrete Mathematics, 6, str. 275–279, PAN  0593539.
  • Skums, P. V .; Suzdal ', S. V .; Tyshkevich, R. I. (2009), „Edge intersection of linear 3-uniform hypergraphs“, Diskrétní matematika, 309: 3500–3517, doi:10.1016 / j.disc.2007.12.082.