Linjegraf af en hypergraf

En linjegraf for en hypergraf  er en graf, hvis toppunktssæt er hypergrafens hyperkantsæt, og to hyperkanter er tilstødende, hvis de har et ikke-tomt skæringspunkt. Med andre ord er linjegrafen for en hypergraf skæringsgrafen for en familie af endelige mængder. Konceptet er en generalisering af en linjegraf af en almindelig graf.

Spørgsmål om linjegrafer af hypergrafer er ofte generaliseringer af spørgsmål om linjegrafer af almindelige grafer. For eksempel kaldes en hypergraf, hvis kanter er af størrelse k , k-uniform' (en 2-uniform hypergraf er en almindelig graf). I hypergrafteori er det ofte naturligt at kræve k -ensartethed. Enhver almindelig graf er en linjegraf af en eller anden hypergraf, men hvis vi fastsætter kantstørrelsen k (antallet af punkter i sættet, der hører til kanten), er ikke hver graf en linjegraf af en eller anden k - ensartet graf. Hovedopgaven er at beskrive linjegrafer for hver .

En hypergraf kaldes lineær , hvis et par hyperkanter højst har et toppunkt i skæringspunktet. Enhver graf er en linjegraf, ikke kun af en hypergraf, men også af en lineær hypergraf [1] .

Linjegrafer af k -ensartede hypergrafer,

Beinecke [2] beskrev linjegraferne for almindelige grafer ved at opremse 9 forbudte inducerede undergrafer (se indgangen på linjegrafer ). Ingen beskrivelse af forbudte inducerede subgrafer er kendt for linjegraferne for k-ensartede hypergrafer for nogen , og Lovas [3] viste, at der ikke er en sådan beskrivelse i form af en endelig liste for k = 3.

Kraus [4] beskrev linjegrafer af almindelige grafer i form af klikdækning ( Se linjegraf ). En global beskrivelse af Kraus-typen for linjegrafer af k -uniforme hypergrafer for enhver er givet af Berge [1] .

Linjegrafer af k -ensartede linjehypergrafer for

En global beskrivelse af Kraus-typen for linjegrafer af k -ensartede linjehypergrafer for enhver er givet af Naik, Rao, Srikhande og Singhi [5] . Samtidig fandt de et endeligt antal forbudte inducerede subgrafer for lineære 3-ensartede hypergrafer med en minimum toppunktsgrad på mindst 69. Metelsky og Tyshkevich [6] og Jakobson, Kezdi, Lekhel [7] forbedrede denne grænse til 19 , mens Skums, Suzdal og Tyszkiewicz [8] reducerede dette til 16. Metelsky og Tyszkiewicz [6] beviste også, at for k > 3 er der ikke en sådan liste for lineære k -ensartede hypergrafer, uanset hvilken grad begrænsning der er pålagt.

Kompleksiteten ved at finde en beskrivelse af lineære k -ensartede hypergrafer er, at der er uendeligt mange forbudte genererede subgrafer. For at give et eksempel, for m > 0, tag en kæde af m diamantgrafer , så diamanterne deler andenordens hjørner, og tilføj nogle hængende knudepunkter, som vist på figuren, for at få en af ​​familierne med minimale forbudte undergrafer [5 ] [9] .

Der er en række interessante beskrivelser af linjegraferne af lineære k -uniforme hypergrafer givet af forskellige forfattere [10] , med forbehold for begrænsninger på minimumsgraden af ​​hjørner eller minimumsgraden af ​​kanter. Den mindste kantgrad for at beskrive linjegrafer af k -ensartede linjehypergrafer for enhver , hvilket ikke er mindre i Naik, Rao, Srikhandes og Sighis arbejde [5] , er reduceret til i Jakobson, Kezdi, Lehels værker [7] ] og Zverovich [11] .

Kompleksiteten i at genkende linjegrafer af lineære k -ensartede hypergrafer uden begrænsninger på minimumsgraden (eller minimumsgraden af ​​kanter) er ukendt. For k = 3 og en minimumsgrad på mindst 19 er genkendelse mulig i polynomisk tid [7] [6] ). Skums, Suzdal og Tyszkiewicz [8] reducerede minimumsgraden til 10.

Der er mange uløste problemer og hypoteser i værkerne af Nike et al., Jacobson et al., Metelsky et al., og Zverovich.

Noter

  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 og 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 og Tyshkevich, 1997 ; Zverovich, 2004
  11. ↑ Zverovich, 2004 .

Litteratur