Grev Moore

Uløste problemer i matematik : Findes der en Moore-graf med omkreds 5 og grad 57?

En Moore-graf er en regulær graf af grad og diameter , hvis antal hjørner er lig med den øvre grænse $d$ $k$

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

En tilsvarende definition af en Moore-graf er en diametergraf med omkreds . En anden ækvivalent definition af en Moore-graf er en graf med omkreds , der har nøjagtig længdecyklusser , hvor , er antallet af hjørner og kanter af . Grafer er faktisk ekstreme med hensyn til antallet af cyklusser, hvis længde er lig med omkredsen af grafen [1] . $k$ $2k+1$ $G$ $g=2k+1$ ${\frac {n}{g}}(m-n+1)$ $g$ $n$ $m$ $G$

Grafer er opkaldt af Alan Hoffman og Robert Singleton [2] efter Edward Moore , som rejste spørgsmålet om at beskrive og klassificere sådanne grafer.

Med det maksimalt mulige antal knudepunkter for en given kombination af grad og diameter, har Moore-grafer det mindst mulige antal knudepunkter for almindelige grafer med en given grad og omkreds. Således er enhver Moore-graf en celle [3] . Formlen for antallet af hjørner i en Moore-graf kan generaliseres til at kunne definere Moore-grafer med lige omkreds, og disse grafer er igen celler.

Grænser for antallet af hjørner efter grad og diameter

Lade være enhver graf med maksimal grad og diameter , så tager vi et træ dannet ved bredde-første søgning , forankret i toppunkt . Dette træ har 1 niveau 0 toppunkt (selve toppunktet ), og maksimalt niveau 1 toppunkter (naboer til toppunktet ). Det næste niveau har et maksimum af hjørner – hver nabo af et toppunkt bruger en kant til at forbinde til toppunkt , så det har et maksimum på naboer på niveau 2. Generelt viser argumenter som dette, at der højst kan være toppunkter på ethvert niveau. Det samlede antal hjørner kan således højst være $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 og Singleton [2] definerede oprindeligt Moore-grafen som en graf, for hvilken denne grænse for antallet af toppunkter nås. Således har enhver Moore-graf det maksimalt mulige antal hjørner blandt alle grafer, hvor graden ikke overstiger , og diameteren er . $d$ $k$

Senere viste Singleton [4] at Moore-grafer kan defineres tilsvarende som en graf med diameter og omkreds . Disse to krav kombineres, hvorfra grafens d -regularitet udledes for nogle . $k$ $2k-1$ $d$

Moore tegner grafer som celler

I stedet for en øvre grænse for antallet af toppunkter i en graf med hensyn til dens maksimale grad og diameter, kan vi bruge en nedre grænse for antallet af toppunkter i form af dens minimumsgrad og omkreds [3] . Antag, at grafen har en minimumsgrad og -omkreds . Vi vælger et vilkårligt startpunkt og forestiller os som før et bredde-første søgetræ med rod på . Dette træ skal have ét toppunkt i niveau 0 (selve toppunktet ) og mindst toppunkter i niveau 1. I niveau 2 (for ) skal der være mindst toppunkter, fordi hvert toppunkt i niveauet har mindst tilbageværende links, og ikke to niveau 1 toppunkter kan ikke være tilstødende eller have niveau 2 toppunkter til fælles, da dette ville skabe en cyklus kortere end omkredsen. Generelt viser lignende argumenter, at der skal være mindst hjørner på ethvert niveau. Således skal det samlede antal hjørner være mindst $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 dette antal hjørner. Hver Moore-graf har omkreds nøjagtigt - den har ikke nok toppunkter til at have en større omkreds, og en kortere cyklus ville resultere i mangel på toppunkter i de første niveauer af nogle bredde-første søgetræer. Således har enhver Moore-graf det mindst mulige antal hjørner blandt alle grafer med en minimumsgrad og diameter - det er en celle . $2k+1$ $k$ $d$ $k$

For en jævn omkreds kan der dannes et lignende bredde-første søgetræ fra midten af den ene kant. Vi får grænsen for det mindste antal hjørner i grafen for denne omkreds med minimumsgraden $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}.

Moore-grafer inkluderer således nogle gange grafer, hvorpå en given grænse nås. Igen er enhver sådan graf en celle.

Eksempler

Hoffman-Singleton- sætningen siger, at enhver Moore-graf med omkreds 5 skal have grad 2, 3, 7 eller 57. Moore-grafer er:

Komplet grafer med n > 2 hjørner. (diameter 1, omkreds 3, grad n-1, rækkefølge ) ${\displaystyle K_{n))$ $n$
ulige cyklusser . (diameter , omkreds , grad 2, rækkefølge 2n+1) $C_{2n+1}$ $n$ $2n+1$
Grev Petersen . (diameter 2, omkreds 5, grad 3, rækkefølge 10)
Jarl af Hoffman-Singleton . (diameter 2, omkreds 5, grad 7, ordre 50)
En hypotetisk graf med diameter 2, omkreds 5, grad 57 og orden 3250, om en sådan graf eksisterer, er i øjeblikket ukendt.

Higman viste, at i modsætning til andre Moore-grafer kan den ukendte graf ikke være vertex-transitiv . Machai og Sheeran viste senere, at rækkefølgen af automorfismer af en sådan graf ikke overstiger 375.

I den generaliserede definition af Moore-grafer, hvor lige omkreds er tilladt, svarer grafer med lige omkreds til incidensgraferne for (muligvis degenererede) generaliserede polygoner . Et par eksempler er lige cyklusser , komplette todelte grafer med omkreds fire, Heawood-grafen med grad 3 og omkreds 6, og Tutt-Coxeter-grafen med grad 3 og omkreds 8. Det er kendt [5] [6] ), at alle Moore grafer undtagen dem, der er anført ovenfor, skal have omkreds 5, 6, 8 eller 12. Tilfældet med lige omkreds følger af Feit-Higmans mulige værdisætning for generaliserede n-goner. $C_{2n}$ ${\displaystyle K_{n,n))$ $n$

Se også

Størrelsesproblem - diameter
Tabel over de største kendte grafer for en given diameter og maksimal grad

Litteratur

Jernej Azarija, Sandi Klavžar. Moores grafer og cyklusser er ekstreme grafer for konvekse cyklusser // Journal of Graph Theory . - 2015. - T. 80 . — S. 34–42 . - doi : 10.1002/jgt.21837 .
Bela Bollobas. Moderne grafteori. - Springer-Verlag , 1998. - V. 184. - ( Graduate Texts in Mathematics ). .
E. Bannai, T. Ito. På endelige Moore-grafer // Tidsskrift for Det Naturvidenskabelige Fakultet, Tokyos Universitet. Sekt. 1A, Matematik. - 1973. - T. 20 . — S. 191–208 . Arkiveret fra originalen den 24. april 2012.
RM Damerell. Om 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 et problem med grafteori // Studia Sci. Matematik. Ungarn.. - 1966. - T. 1 . — S. 215–235 . .
Alan J. Hoffman, Robert R. Singleton. Moore-grafer med diameter 2 og 3 // IBM Journal of Research and Development. - 1960. - V. 5 , no. 4 . — S. 497–504 . - doi : 10.1147/rd.45.0497 .
Martin Macaj, Jozef Širan. Søg efter egenskaber for den manglende Moore-graf // Lineær algebra og dens applikationer . - 2010. - T. 432 . — S. 2381–2398 . - doi : 10.1016/j.laa.2009.07.018 . .
Robert R. Singleton. Der er ingen uregelmæssig Moore-graf // American Mathematical Monthly . - 1968. - T. 75 , no. 1 . — S. 42–43 . - doi : 10.2307/2315106 .