Earl of Grey

Den grå grafen  är en tvådelad oriktad graf med 54 hörn och 81 kanter. Grafen är kubisk  - vilken vertex som helst tillhör exakt tre kanter. Grafen upptäcktes av Gray 1932 ( utan publicering), och upptäcktes sedan oberoende av Bouwer 1968 som svar på en fråga som ställdes av Folkman 1967. Den grå grafen är anmärkningsvärd som historiskt sett det första exemplet på en kubisk graf som har den algebraiska egenskapen kant men inte vertextransitivitet.

Det kromatiska numret på den grå grafen är 2, det kromatiska indexet  är 3 och radien och diametern är 6. Det är också en 3-hörnkopplad och 3-kantsansluten icke- plan graf .

Byggnad

Den grå grafen kan konstrueras [1] från 27 punkter av ett 3×3×3 gitter och 27 linjer parallella med axlarna och som går genom dessa punkter. Denna uppsättning punkter och linjer bildar en projektiv konfiguration  - exakt tre linjer passerar genom varje punkt, och exakt tre punkter ligger på varje linje. Den grå grafen är Levi-grafen för denna konfiguration. Grafen har en vertex för varje punkt och för varje linje i denna konfiguration, och en kant för varje punkt-linjepar om punkten ligger på linjen. Denna konstruktion kan generaliseras (Bauwer 1972) till vilken dimension som helst , vilket ger -valens Lévy-grafer med algebraiska egenskaper som liknar de för Gray-grafen.

Den kan också konstrueras som en Levi-graf för kanterna och triangulära ytor av någon lokalt toroidformad abstrakt regelbunden 4-polytop [2] .

Marusic och Pisanski [3] gav några alternativa metoder för att konstruera en grå graf. Liksom alla andra tvådelade grafer innehåller den grå grafen inte cykler med udda längd, och den innehåller inte heller cykler med fyra eller sex hörn, så omkretsen på en grå graf är 8. Den enklaste orienterade ytan i vilken en grå graf kan bäddas in är av släkte 7 [4] .

Den grå grafen är Hamiltonsk och kan konstrueras från LCF-notation :

Algebraiska egenskaper

Automorfigruppen i grafen Grå är en grupp av ordningen 1296. Den verkar transitivt på grafens kanter, men inte på dess hörn - det finns automorfismer som tar vilken kant som helst till vilken annan kant som helst, men det finns inga automorfismer som tar någon vertex till någon annan. Vertices som motsvarar konfigurationen som ligger bakom grafen kan endast vara symmetriska till hörn som motsvarar konfigurationspunkter, och hörn som motsvarar linjer är symmetriska endast till hörn som motsvarar linjer. Således är den grå grafen en semisymmetrisk grupp och är den minsta möjliga kubiska semisymmetriska grafen.

Det karakteristiska polynomet för den grå grafen är:

Galleri

• Earl of Grey

• Det kromatiska talet för Count Gray är 2.

• det kromatiska indexet för den grå grafen är 3.

• Konfigurationen som ligger bakom Graph Gray.

Anteckningar

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

Länkar

• En kant men inte 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 inte vertex transitiva reguljära grafer // Journal of Combinatorial Theory, Series B. - 1972. - Vol. 12 . — S. 32–40 . - doi : 10.1016/0095-8956(72)90030-5 . .
• J Folkman. Regelbundna linjesymmetriska grafer // Journal of Combinatorial Theory. - 1967. - T. 3 , nummer. 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äktet för den grå grafen är 7 // European Journal of Combinatorics. - 2005. - T. 26 , nr. 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 , nr. 3 . — S. 421–435 . - doi : 10.1016/j.jcta.2006.06.007 .
• Weisstein, Eric W. Gray Graph  (engelska) på Wolfram MathWorld- webbplatsen .
• The Grey Graph är den minsta grafen i sitt slag Arkiverad 22 februari 2014 på Wayback Machine , från MathWorld .