Moore graf

Olöst problem i matematik :

Finns det en Moore-graf med omkrets 5 och grad 57?

(fler olösta problem i matematik)

I grafteorin är en Moore-graf en vanlig graf vars omkrets (den kortaste cykellängden ) är mer än två gånger dess diameter (avståndet mellan de två längsta hörnen ). Om graden av en sådan graf är d och dess diameter är k , måste dess omkrets vara lika med 2 k + 1 . Detta gäller för en graf med grad d och diameter k , om och endast om dess antal hörn är lika med

$1+d\sum _{i=0}^{k-1}(d-1)^{i},$

en övre gräns för största möjliga antal hörn i någon graf med denna grad och diameter. Därför löser dessa grafer gradens diameterproblem för deras parametrar.

En annan ekvivalent definition av en Moore-graf G är att den har omkrets g = 2 k + 1 och exakt n / g ( m – n + 1) cykler med längden g , där n och m är antalet hörn respektive kanter av G. _ De är faktiskt extrema med avseende på antalet cykler vars längd är grafens omkrets.

Moore-grafer döptes av Hoffman & Singleton (1960) efter Edward F. Moore , som ställde frågan om att beskriva och klassificera dessa grafer.

Förutom att ha maximalt möjliga antal hörn för en given kombination av grad och diameter, har Moore-grafer minsta möjliga antal hörn för en vanlig graf med given grad och omkrets. Det vill säga, vilken Moore-graf som helst är en bur . Formeln för antalet hörn i en Moore-graf kan generaliseras för att möjliggöra en definition av Moore-grafer med jämn omkrets såväl som udda omkrets, och återigen är dessa grafer burar.

Begränsa hörn efter grad och diameter

Petersen -grafen som en Moore-graf. Varje sökträd med bredd som först har d ( d − 1) ⁱ hörn på sin i :e nivå.

Låt G vara vilken graf som helst med maximal grad d och diameter k , och betrakta trädet som bildas av först breddsökning med början från valfri vertex v . Det här trädet har 1 hörn på nivå 0 ( v ) och högst d hörn på nivå 1 ( grannarna till v ). I nästa nivå finns det som mest d ( d − 1) hörn: varje granne till v använder en av sina grannar för att ansluta till v och kan därför ha högst d − 1 grannar på nivå 2. I allmänhet är ett liknande argument visar att på vilken nivå 1 ≤ i ≤ k som helst kan det finnas högst d ( d − 1) ^{i −1} hörn. Således kan det totala antalet hörn vara högst

$1+d\sum _{i=0}^{k-1}(d-1)^{i}.$

Hoffman & Singleton (1960) definierade ursprungligen en Moore-graf som en graf för vilken denna gräns för antalet hörn uppfylls exakt. Därför har varje Moore-graf det maximala antalet hörn som är möjligt bland alla grafer med maximal grad d och diameter k .

Senare visade Singleton (1968) att Moore-grafer på motsvarande sätt kan definieras som att ha diametern k och omkretsen 2 k + 1 ; dessa två krav kombineras för att tvinga grafen att vara d -regelbunden för vissa d och för att uppfylla vertexräkningsformeln.

Moore grafer som burar

Istället för att övre gränsen för antalet hörn i en graf i termer av dess maximala grad och dess diameter, kan vi via liknande metoder beräkna en nedre gräns för antalet hörn i termer av dess minimigrad och dess omkrets . Antag att G har minsta grad d och omkrets 2 k + 1 . Välj godtyckligt en startpunkt v och betrakta som tidigare sökträdet med bredd-först rotat vid v . Detta träd måste ha en vertex på nivå 0 ( v sig själv), och minst d hörn på nivå 1. På nivå 2 (för k > 1 ), måste det finnas minst d ( d − 1) hörn, eftersom varje vertex vid nivå 1 nivå 1 har minst d − 1 kvarvarande närliggande punkter att fylla, och inga två hörn på nivå 1 kan ligga intill varandra eller till en delad vertex på nivå 2 eftersom det skulle skapa en cykel kortare än den antagna omkretsen. I allmänhet visar ett liknande argument att på vilken nivå 1 ≤ i ≤ k som helst måste det finnas minst d ( d − 1) ⁱ hörn. Alltså måste det totala antalet hörn vara minst

$1+d\sum _{i=1}^{k-1}(d-1)^{i}.$

I en Moore-graf uppfylls denna gräns för antalet hörn exakt. Varje Moore-graf har en omkrets exakt 2 k + 1 : den har inte tillräckligt med hörn för att ha högre omkrets, och en kortare cykel skulle göra att det blir för få hörn i de första k -nivåerna av ett brett första sökträd. Därför har varje Moore-graf det minsta antalet hörn som är möjligt bland alla grafer med minsta grad d och omkrets 2 k + 1 : det är en bur .

För jämn omkrets 2 k , kan man på liknande sätt bilda ett bredd-första sökträd med början från mittpunkten av en enda kant. Den resulterande gränsen på det minsta antalet hörn i en graf av denna omkrets med minsta grad d är

$2\sum _{i=0}^{k-1}(d-1)^{i}=1+(d-1)^{k-1}+d\sum _{i=0 }^{k-2}(d-1)^{i}.$

(Höger sida av formeln räknar istället antalet hörn i ett bredd första sökträd med början från en enda hörn, vilket tar hänsyn till möjligheten att en vertex i trädets sista nivå kan ligga intill d hörn i föregående nivå .) Således definieras Moore-graferna ibland som att de inkluderar de grafer som exakt uppfyller denna gräns. Återigen, varje sådan graf måste vara en bur.

Exempel

Hoffman -Singleton-satsen säger att alla Moore-grafer med omkrets 5 måste ha grad 2, 3, 7 eller 57. Moore-graferna är:

• De kompletta graferna K _n på n > 2 noder (diameter 1, omkrets 3, grad n − 1 , ordning n )
• De udda cyklerna C _{2 n +1} (diameter n , omkrets 2 n + 1 , grad 2, ordning 2 n + 1 )
• Petersen -grafen (diameter 2, omkrets 5, grad 3, ordning 10)
• Hoffman –Singleton-grafen (diameter 2, omkrets 5, grad 7, ordning 50)
• En hypotetisk graf med diameter 2, omkrets 5, grad 57 och ordning 3250, vars existens är okänd

Även om alla kända Moore-grafer är vertextransitiva grafer , kan den okända (om den existerar) inte vara vertextransitiv, eftersom dess automorfismgrupp kan ha ordning högst 375, mindre än antalet hörn.

Om den generaliserade definitionen av Moore-grafer som tillåter jämn omkretsgrafer används, motsvarar Moore-graferna med jämn omkrets incidensgrafer för (eventuellt degenererade) generaliserade polygoner . Några exempel är de jämna cyklerna C _{2 n} , de kompletta tvådelade graferna K _{n , n} med omkrets fyra, Heawood-grafen med grad 3 och omkrets 6, och Tutte–Coxeter-grafen med grad 3 och omkrets 8. Mer allmänt är det känt att, förutom graferna som listas ovan, måste alla Moore-grafer ha omkrets 5, 6, 8 eller 12. Fallet med jämn omkrets följer också av Feit-Higman-satsen om möjliga värden på n för en generaliserad n -gon .

Se även

• Tabell över de största kända graferna för en given diameter och maximal grad

Anteckningar

• Azarija, Jernej; Klavžar, Sandi (2015), "Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles", Journal of Graph Theory , 80 : 34–42, arXiv : 1210.6342 , doi : 10.1002/jgt.212C87 3 , S  
•   Bannai, E.; Ito, T. (1973), "On finite Moore graphs" , Journal of the Science of Science, University of Tokyo. Sekt. 1 A, Mathematics , 20 : 191–208, MR 0323615 , arkiverad från originalet 2012-04-24
• Bollobás, Béla (1998), Modern Graph Theory , Graduate Texts in Mathematics , vol. 184, Springer-Verlag .
•    Dalfó, C. (2019), "A survey on the missing Moore graph" (PDF) , Linear Algebra and Its Applications , 569 : 1–14, doi : 10.1016/j.laa.2018.12.035 , hdl : 212121212 , MR 3901732 , S2CID 126689579
• Damerell, RM (1973), "On Moore graphs", Mathematical Proceedings of the Cambridge Philosophical Society , 74 ( 2): 227–236, Bibcode : 1973PCPS...74..227D , doi : 10.1017/S030500041 , 8505004101 , 850500401  
• Erdős, Paul ; Rényi, Alfréd ; Sós, Vera T. (1966), "On a problem of graph theory" (PDF) , Studia Sci. Matematik. Ungern. , 1 : 215–235, arkiverad från originalet (PDF) 2016-03-09 , hämtad 2010-02-23 .
•   Hoffman, Alan J .; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3", IBM Journal of Research and Development , 5 (4): 497–504, doi : 10.1147/rd.45.0497 , MR 0140437
• Mačaj, Martin; Širáň, Jozef (2010), "Search for properties of the missing Moore graph", Linear Algebra and Its Applications , 432 (9): 2381–2398, doi : 10.1016/j.laa.2009.07.018 .
•    Singleton, Robert R. (1968), "There is no irregular Moore graph", American Mathematical Monthly , 75 (1): 42–43, doi : 10.2307/2315106 , JSTOR 2315106 , MR 0225679

externa länkar

• Brouwer och Haemers: Spektra av grafer
• Eric W. Weisstein , Moore Graph ( Hoffman-Singleton Theorem ) på MathWorld .