Earl of Grey

Den grå graf  er en todelt urettet graf med 54 hjørner og 81 kanter. Grafen er kubisk  - ethvert toppunkt hører til præcis tre kanter. Grafen blev opdaget af Gray i 1932 (uden offentliggørelse), derefter opdaget uafhængigt af Bouwer i 1968 som svar på et spørgsmål stillet af Folkman i 1967. Den grå graf er bemærkelsesværdig som historisk set det første eksempel på en kubisk graf, der har den algebraiske egenskab kant, men ikke vertex transitivitet.

Det kromatiske tal for den grå graf er 2, det kromatiske indeks  er 3, og radius og diameter er 6. Det er også en 3-kant-forbundet og 3-kant-forbundet ikke- plan graf .

Konstruktion

Den grå graf kan konstrueres [1] ud fra 27 punkter af et 3×3×3 gitter og 27 linjer parallelt med akserne og passerer gennem disse punkter. Dette sæt af punkter og linjer danner en projektiv konfiguration  - nøjagtigt tre linjer passerer gennem hvert punkt, og præcis tre punkter ligger på hver linje. Den grå graf er Levi-grafen for denne konfiguration. Grafen har et toppunkt for hvert punkt og for hver linje i denne konfiguration og en kant for hvert punkt-linjepar, hvis punktet ligger på linjen. Denne konstruktion kan generaliseres (Bauwer 1972) til enhver dimension , hvilket giver -valens Lévy-grafer med algebraiske egenskaber svarende til dem i den grå graf.

Den kan også konstrueres som en Levi-graf for kanterne og trekantede flader af en lokalt toroidformet abstrakt regulær 4-polytop [2] .

Marusic og Pisanski [3] gav nogle alternative metoder til at konstruere en grå graf. Som enhver anden todelt graf indeholder den grå graf ikke cyklusser med ulige længder, og den indeholder heller ikke cyklusser med fire eller seks hjørner, så omkredsen af ​​en grå graf er 8. Den enkleste orienterede overflade, som en grå graf kan indlejres i er af slægt 7 [4] .

Den grå graf er Hamiltonsk og kan konstrueres ud fra LCF-notation :

Algebraiske egenskaber

Automorfigruppen i grafen Grå er en gruppe af orden 1296. Den virker transitivt på grafens kanter, men ikke på dens hjørner - der er automorfier, der tager en hvilken som helst kant til enhver anden kant, men der er ingen automorfier, der tager nogen toppunkt til enhver anden. Hjørner svarende til den konfiguration, der ligger til grund for grafen, kan kun være symmetriske med knudepunkter svarende til konfigurationspunkter, og knudepunkter svarende til linjer er kun symmetriske til knudepunkter svarende til linjer. Således er den grå graf en semisymmetrisk gruppe og er den mindst mulige kubiske semisymmetriske graf.

Det karakteristiske polynomium for den grå graf er:

Galleri

• Earl of Grey

• Det kromatiske tal for Count Grey er 2.

• det kromatiske indeks for den grå graf er 3.

• Konfigurationen, der ligger til grund for Graph Gray.

Noter

1. ↑ Bouwer, 1972 .
2. ↑ Monson, Pisanski, Schulte, Ivic-Weiss, 2007 .
3. ↑ Marusic, Pisanski, 2000 .
4. ↑ Marušič, Pisanski, Wilson, 2005 .

Links

• En kant, men ikke vertex transitiv kubisk graf // Bulletin of the Canadian Mathematical Society. - 1968. - T. 11 . — S. 533–535 . - doi : 10.4153/CMB-1968-063-0 . .
• IZ Bouwer. På kant, men ikke vertex transitive regulære grafer // Journal of Combinatorial Theory, Series B. - 1972. - Vol. 12 . — S. 32–40 . - doi : 10.1016/0095-8956(72)90030-5 . .
• J Folkman. Regelmæssige linjesymmetriske grafer // Journal of Combinatorial Theory. - 1967. - T. 3 , udg. 3 . — S. 533–535 . - doi : 10.1016/S0021-9800(67)80069-3 . .
• Dragan Marušic, Tomaž Pisanski. The Grey graph revisited  // Journal of Graph Theory. - 2000. - T. 35 . — S. 1–7 . - doi : 10.1002/1097-0118(200009)35:1<1::AID-JGT1>3.0.CO;2-7 . .
• Dragan Marusic, Tomaž Pisanski, Steve Wilson. Slægten for den grå graf er 7 // European Journal of Combinatorics. - 2005. - T. 26 , no. 3–4 . — S. 377–385 . - doi : 10.1016/j.ejc.2004.01.015 . .
• B. Monson, T. Pisanski, E. Schulte, A. Ivic-Weiss. Semisymmetric Graphs from Polytopes // Journal of Combinatorial Theory, Series A. - 2007. - Vol. 114 , no. 3 . — S. 421–435 . - doi : 10.1016/j.jcta.2006.06.007 .
• Weisstein, Eric W. Gray Graph  (engelsk) på Wolfram MathWorld- webstedet .
• Den grå graf er den mindste graf af sin slags arkiveret 22. februar 2014 på Wayback Machine , fra MathWorld .