Greve Moore

Olösta problem i matematik : Finns det en Moore-graf med omkrets 5 och grad 57?

En Moore-graf är en vanlig graf av grad och diameter , vars antal hörn är lika med den övre gränsen $d$ $k$

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

En motsvarande definition av en Moore-graf är en diametergraf med omkrets . En annan likvärdig definition av en Moore-graf är en graf med omkrets som har exakt längdcykler , där är antalet hörn och kanter av . Grafer är faktiskt extrema med avseende på antalet cykler vars längd är lika med grafens omkrets [1] . $k$ $2k+1$ $G$ $g=2k+1$ ${\frac {n}{g}}(m-n+1)$ $g$ $n$ $m$ $G$

Grafer är uppkallade av Alan Hoffman och Robert Singleton [2] efter Edward Moore , som tog upp frågan om att beskriva och klassificera sådana grafer.

Med maximalt möjliga antal hörn för en given kombination av grad och diameter, har Moore-grafer det minsta möjliga antalet hörn för vanliga grafer med en given grad och omkrets. Således är vilken Moore-graf som helst en cell [3] . Formeln för antalet hörn i en Moore-graf kan generaliseras för att kunna definiera Moore-grafer med jämn omkrets, och dessa grafer är återigen celler.

Gränser för antalet hörn efter grad och diameter

Låt vara vilken graf som helst med maximal grad och diameter , då tar vi ett träd som bildas av bredd-först sökning , rotat i vertex . Detta träd har 1 vertex på nivå 0 (själva vertex ), och maximalt nivå 1 vertex (grannar till vertex ). Nästa nivå har ett maximum av hörn – varje granne till en vertex använder en kant för att ansluta till vertex , så den har maximalt nivå 2 grannar. I allmänhet visar argument som detta att det kan finnas högst hörn på vilken nivå som helst. Således kan det totala antalet hörn vara högst $G$ $d$ $k$ $v$ $v$ $d$ $v$ $d(d-1)$ $v$ $v$ $d-1$ ${\displaystyle 1\leq {i}\leq {k))$ ${\displaystyle d(d-1)^{i))$

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

Hoffman och Singleton [2] definierade ursprungligen Moore-grafen som en graf för vilken denna gräns för antalet hörn nås. Således har varje Moore-graf maximalt möjliga antal hörn bland alla grafer där graden inte överstiger , och diametern är . $d$ $k$

Senare visade Singleton [4] att Moore-grafer kan definieras på samma sätt som en graf med diameter och omkrets . Dessa två krav kombineras, från vilka grafens d -regelbundenhet härleds för vissa . $k$ $2k-1$ $d$

Moore visar grafer som celler

Istället för en övre gräns för antalet hörn i en graf i termer av dess maximala grad och diameter, kan vi använda en nedre gräns för antalet hörn i termer av dess minimigrad och omkrets [3] . Antag att grafen har en lägsta grad och omkrets . Vi väljer ett godtyckligt startpunkt och föreställer oss, som tidigare, ett sökträd med breddförst rotat på . Detta träd måste ha en vertex i nivå 0 (själva vertex ) och minst vertex i nivå 1. I nivå 2 (för ) måste det finnas minst vertex, eftersom varje vertex i nivån har åtminstone återstående länkar, och ingen två hörn på nivå 1 kan inte vara intill varandra eller ha gemensamma hörn på nivå 2, eftersom detta skulle skapa en cykel kortare än omkretsen. I allmänhet visar liknande argument att det måste finnas åtminstone hörn på vilken nivå som helst. Alltså måste det totala antalet hörn vara minst $G$ $d$ $2k+1$ $v$ $v$ $v$ $d$ $k>1$ $d(d-1)$ $l$ $d-1$ ${\displaystyle 1\leq {i}\leq {k))$ ${\displaystyle d(d-1)^{i))$

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

I Moore-grafen nås detta antal hörn. Varje Moore-graf har omkrets exakt - den har inte tillräckligt med hörn för att ha en större omkrets, och en kortare cykel skulle resultera i en brist på hörn i de första nivåerna av vissa bredd-första sökträd. Således har varje Moore-graf minsta möjliga antal hörn bland alla grafer med en minsta grad och diameter - det är en cell . $2k+1$ $k$ $d$ $k$

För en jämn omkrets kan ett liknande bredd-första sökträd bildas från mitten av ena kanten. Vi får gränsen för det minsta antalet hörn i grafen för denna omkrets med minsta graden $2k$ $d$

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

Således inkluderar Moore-grafer ibland grafer där en given gräns nås. Återigen är varje sådan graf en cell.

Exempel

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

Komplettera grafer med n > 2 hörn. (diameter 1, omkrets 3, grad n-1, ordning ) ${\displaystyle K_{n))$ $n$
udda cykler . (diameter , omkrets , grad 2, ordning 2n+1) $C_{2n+1}$ $n$ $2n+1$
Greve Petersen . (diameter 2, omkrets 5, grad 3, ordning 10)
Earl of Hoffman-Singleton . (diameter 2, omkrets 5, grad 7, ordning 50)
En hypotetisk graf med diameter 2, omkrets 5, grad 57 och ordning 3250, om en sådan graf existerar är för närvarande okänt.

Higman visade att, till skillnad från andra Moore-grafer, kan den okända grafen inte vara vertextransitiv . Machai och Sheeran visade senare att ordningen för automorfismer för en sådan graf inte överstiger 375.

I den generaliserade definitionen av Moore-grafer, där jämn omkrets är tillåten, motsvarar grafer med jämn omkrets incidensgraferna för (eventuellt degenererade) generaliserade polygoner . Några exempel är jämna cykler , kompletta tvådelade grafer med omkrets fyra, Heawood-grafen med grad 3 och omkrets 6, och Tutt-Coxeter-grafen med grad 3 och omkrets 8. Det är känt [5] [6] ) att alla Moore grafer förutom de som listas ovan måste ha omkrets 5, 6, 8 eller 12. Fallet med jämn omkrets följer av Feit-Higmans möjliga värdesats för generaliserade n-goner. $C_{2n}$ ${\displaystyle K_{n,n))$ $n$

Se även

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

Litteratur

Jernej Azarija, Sandi Klavžar. Moores grafer och cykler är extrema grafer för konvexa cykler // Journal of Graph Theory . - 2015. - T. 80 . — S. 34–42 . - doi : 10.1002/jgt.21837 .
Bela Bollobas. Modern grafteori. - Springer-Verlag , 1998. - V. 184. - ( Graduate Texts in Mathematics ). .
E. Bannai, T. Ito. På ändliga Moore-grafer // Journal of the Science of Science, University of Tokyo. Sekt. 1A, Matematik. - 1973. - T. 20 . — S. 191–208 . Arkiverad från originalet den 24 april 2012.
RM Damerell. På Moore-grafer // Mathematical Proceedings of the Cambridge Philosophical Society. - 1973. - T. 74 . — S. 227–236 . - doi : 10.1017/S0305004100048015 .
Paul Erdős, Alfred Rényi, Vera T. Sos. Om ett problem med grafteori // Studia Sci. Matematik. Ungern.. - 1966. - T. 1 . — S. 215–235 . .
Alan J. Hoffman, Robert R. Singleton. Moore grafer med diameter 2 och 3 // IBM Journal of Research and Development. - 1960. - V. 5 , nr. 4 . — S. 497–504 . - doi : 10.1147/rd.45.0497 .
Martin Macaj, Jozef Širan. Sök efter egenskaper för den saknade Moore-grafen // Linjär algebra och dess tillämpningar . - 2010. - T. 432 . — S. 2381–2398 . - doi : 10.1016/j.laa.2009.07.018 . .
Robert R. Singleton. Det finns ingen oregelbunden Moore-graf // American Mathematical Monthly . - 1968. - T. 75 , nr. 1 . — S. 42–43 . - doi : 10.2307/2315106 .

Länkar

Brouwer och Haemers: Spectra of graphs Arkiverad 3 oktober 2017 på Wayback Machine
Weisstein, Eric W. Moore Graph (engelska) på Wolfram MathWorld- webbplatsen .
Weisstein, Eric W. Hoffman-Singleton Theorem (engelska) på Wolfram MathWorld -webbplatsen .