En Moore-graf är en vanlig graf av grad och diameter , vars antal hörn är lika med den övre gränsen
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] .
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.
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
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 .
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 .
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
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 .
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
Således inkluderar Moore-grafer ibland grafer där en given gräns nås. Återigen är varje sådan graf en cell.
Hoffman-Singleton- satsen säger att alla Moore-grafer med omkrets 5 måste ha grad 2, 3, 7 eller 57. Moore-grafer är:
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.