Plan överdrag

Grafen C är en plan täckning av grafen H . Täckkartan indikeras av vertexfärgerna.

I grafteorin är en plan täckning av en finit graf G en finit täckande graf för G som i sig är en plan graf . Varje graf som kan bäddas in i det projektiva planet har ett plant lock; en olöst gissning av Seiya Negami säger att dessa är de enda graferna med plana omslag.

Förekomsten av ett plant lock är en minor-closed graph-egenskap , och kan därför karakteriseras av ändligt många förbjudna minderåriga , men den exakta uppsättningen av förbjudna minderåriga är inte känd. Av samma anledning finns det en polynomtidsalgoritm för att testa om en given graf har en plan täckning, men en explicit beskrivning av denna algoritm är inte känd.

Definition

En täckande karta från en graf C till en annan graf H kan beskrivas med en funktion f från C: s hörn till H :s hörn som, för varje vertex v i C , ger en bijektion mellan grannarna till v och grannarna till f ( v ). Om H är en sammankopplad graf måste varje vertex av H ha samma antal förbilder i C ; detta nummer kallas kartans lager , och C kallas en täckande graf av G . Om C och H båda är ändliga, och C är en plan graf , kallas C en plan täckning av H .

Exempel

Att identifiera par av motsatta hörn av dodekaedern ger en täckande karta till Petersen-grafen

Grafen för dodekaedern har en symmetri som kartlägger varje vertex till den antipoda vertexen. Uppsättningen av antipoda par av hörn och deras närliggande områden kan i sig ses som en graf, Petersen-grafen . Dodekaedern bildar en plan täckning av denna icke-plana graf. Som det här exemplet visar är inte varje graf med ett plant lock i sig plan. Men när en plan graf täcker en icke-plan, måste lagret vara ett jämnt tal .

Det tvåsidiga prismat kan bilda ett 2-lagers hölje av det hexagonala prismat , ett 3-skikts hölje av kuben eller ett 4-skikts hölje av det triangulära prismat .

Grafen för ett k -gonalt prisma har 2 k hörn och är plan med två k -gonytor och k fyrsidiga ytor. Om k = ab , med a ≥ 2 och b ≥ 3, så har den en a -lagers täckande karta till ett b -fonalt prisma, där två hörn av k -prismat är mappade till samma vertex av b -prismat om de båda tillhör samma k -gonala yta och avståndet från den ena till den andra är en multipel av b . Till exempel kan det tvåsidiga prismat bilda ett 2-lagers hölje av det hexagonala prismat , ett 3-skikts hölje av kuben eller ett 4-skikts hölje av det triangulära prismat . Dessa exempel visar att en graf kan ha många olika plana omslag och kan vara det plana omslaget för många andra grafer. Dessutom visar de att skiktet av ett plant lock kan vara godtyckligt stort. De är inte de enda höljena som involverar prismor: till exempel kan det hexagonala prismat också täcka en icke-plan graf, verktygsgrafen K 3,3 , genom att identifiera antipoda par av hörn.

Skyddsbevarande operationer

Om en graf H har en plan täckning, så har varje graf-moll av H också . Ett mindre G av H kan bildas genom att ta bort kanter och hörn från H , och genom att dra ihop kanterna på H . Den täckande grafen C kan transformeras på samma sätt: för varje raderad kant eller vertex i H , radera dess förbild i C och för varje sammandragen kant eller vertex i H , dra ihop dess förbild i C . Resultatet av att tillämpa dessa operationer på C är en mindre av C som täcker G . Eftersom varje moll i en plan graf i sig själv är plan, ger detta en plan täckning av moll G .

Eftersom graferna med plana lock är stängda under operationen att ta minderåriga, följer det av Robertson-Seymour-satsen att de kan karakteriseras av en ändlig uppsättning förbjudna minderåriga . En graf är en förbjuden minor för den här egenskapen om den inte har något plant omslag, men alla dess minderåriga har plana omslag. Denna karaktärisering kan användas för att bevisa existensen av en polynomisk tidsalgoritm som testar förekomsten av ett plant hölje, genom att söka efter var och en av de förbjudna minderåriga och returnera att en plan hölje endast existerar om denna sökning inte lyckas hitta någon av dem. Men eftersom den exakta uppsättningen av förbjudna minderåriga för den här egenskapen inte är känd, är detta bevis på existens icke-konstruktivt och leder inte till en explicit beskrivning av uppsättningen förbjudna minderåriga eller av algoritmen baserad på dem.

En annan grafoperation som bevarar existensen av ett plant lock är Y-Δ-transformen , som ersätter valfri grad-tre vertex av en graf H med en triangel som förbinder dess tre grannar. Det omvända till denna transformation, en Δ-Y-transformation, bevarar emellertid inte nödvändigtvis plana höljen.

Dessutom kommer en osammanhängande förening av två grafer som har omslag också att ha en täckning, bildad som den disjunkta föreningen av de täckande graferna. Om de två omslagen har samma skikt som varandra, kommer detta också att vara skiktet i deras förening.

Negamis gissning

Olöst problem i matematik :

Har varje sammankopplad graf med ett plant lock en inbäddning i det projektiva planet?

(fler olösta problem i matematik)

Om en graf H har en inbäddning i det projektiva planet , så har den nödvändigtvis ett plant lock, givet av förbilden av H i det orienterbara dubbla locket av det projektiva planet, vilket är en sfär. Negami (1986) bevisade, omvänt, att om en ansluten graf H har ett tvåskiktigt plant hölje så måste H ha en inbäddning i det projektiva planet. Antagandet att H är anslutet är nödvändigt här, eftersom en disjunkt förening av projektiva-plana grafer kanske inte i sig är projektiv-planar men kommer fortfarande att ha ett plant lock, den disjunkta föreningen av de orienterbara dubbla locken.

En vanlig täckning av en graf H är en som kommer från en grupp av symmetrier i dess täckande graf: förbilderna av varje vertex i H är en omloppsbana av gruppen. Negami (1988) bevisade att varje sammankopplad graf med ett plant regelbundet lock kan bäddas in i det projektiva planet. Baserat på dessa två resultat antog han att i själva verket varje sammankopplad graf med en plan täckning är projektiv. Från och med 2013 är denna gissning fortfarande olöst. Den är också känd som Negamis "1-2-∞-förmodan", eftersom den kan omformuleras till att det minsta lagret av ett plant hölje, om det finns, måste vara antingen 1 eller 2.

K 1,2,2,2 , det enda möjliga minimala motexemplet till Negamis gissningar

Liksom graferna med plana omslag kan graferna med projektiva planinbäddningar karakteriseras av förbjudna minderåriga. I det här fallet är den exakta uppsättningen av förbjudna minderåriga känd: det finns 35 av dem. 32 av dessa är anslutna, och en av dessa 32 grafer uppträder nödvändigtvis som en mindre i varje ansluten icke-projektiv-plan graf. Sedan Negami gjorde sin gissning har det bevisats att 31 av dessa 32 förbjudna minderåriga antingen inte har plana höljen eller kan reduceras med Y-Δ-transformationer till en enklare graf på denna lista. Den återstående grafen för vilken detta ännu inte har gjorts är K 1,2,2,2 , en apexgraf med sju vertex som bildar skelettet av en fyrdimensionell oktaedrisk pyramid . Om K 1,2,2,2 kunde visas inte ha några plana höljen, skulle detta fullborda ett bevis på gissningen. Å andra sidan, om gissningen är falsk, K 1,2,2,2 nödvändigtvis vara dess minsta motexempel.

En relaterad gissning av Michael Fellows , som nu är löst, gäller plana emulatorer , en generalisering av plana omslag som kartlägger grannskapsområden surjektivt snarare än bijektivt. Graferna med plana emulatorer, som de med plana lock, är stängda under mindre och Y-Δ-transformeringar. 1988, oberoende av Negami, antog Fellows att graferna med plana emulatorer är exakt de grafer som kan bäddas in i det projektiva planet. Gissningen är sann för vanliga emulatorer, som kommer från automomorfismer av den underliggande täckande grafen, med ett resultat som är analogt med resultatet av Negami (1988) för vanliga plana omslag. Flera av de 32 anslutna förbjudna minors för projektiva-plana grafer visar sig dock ha plana emulatorer. Därför är Fellows gissningar falska. Att hitta en hel uppsättning förbjudna minderåriga för förekomsten av plana emulatorer är fortfarande ett öppet problem.

Anteckningar

Sekundära källor om Negamis gissningar

  •    Hliněný, Petr (2010), "20 years of Negami's planar cover conjecture" (PDF) , Graphs and Combinatorics , 26 ( 4): 525–536, doi : 10.1007 /s00373-010-0934-9 , S 42C 526 69 526 . Sidnummer i anteckningar hänvisar till den förtryckta versionen.
  •   Huneke, John Philip (1993), "A conjecture in topological graph theory", Graph Structure Theory (Seattle, WA, 1991) , Contemporary Mathematics, vol. 147, Providence, RI: American Mathematical Society, s. 387–389, doi : 10.1090/conm/147/01186 , MR 1224718 .

Primära källor om plana omslag

Stödlitteratur

Hämtad från " https://en.wikipedia.org/w/index.php?title=Planar_cover&oldid=1032090967 "