McGee gróf

McGee gróf
Valaki után elnevezve WF McGee
Csúcsok 24
borda 36
Sugár négy
Átmérő négy
Heveder 7
Automorfizmusok 32
Kromatikus szám 3
Kromatikus index 3
Tulajdonságok köbös Hamilton
-sejt
 Médiafájlok a Wikimedia Commons oldalon

A gráfelméletben a McGee gráf vagy (3-7)-cella egy 3 - reguláris gráf 24 csúcsgal és 36 éllel. [egy]

McGee gráf az egyetlen (3,7) -cella (legkisebb köbméter 7-es kerülettel). Ez a legkisebb nem Moore-gráf köbös cella .

Először Horst Sachs fedezte fel, de nem publikálták [2] , a grafikon McGee ( WF McGee ) nevéhez fűződik , aki 1960 -ban publikálta az eredményt [3] . Később, 1966 - ban William Thomas Tutt bebizonyította, hogy ez az egyetlen (3,7) cella [4] [5] [6] .

A legkisebb, 1-8 keresztezéses köbös gráfok ismertek ( A110507 szekvencia az OEIS -ben ), a legkisebb 8 keresztezéses gráf a McGee gráf. 5 nemizomorf, 24-es rendű köbös gráf létezik 8 keresztezéssel [7] , ezek egyike az általánosított Petersen-gráf G (12,5), más néven Nauru gráf [8] .

A McGee gráf sugara 4, átmérője 4, kromatikus száma 3, kromatikus indexe 3. Ezenkívül 3 csúcshoz és 3 élhez kapcsolódik .

Algebrai tulajdonságok

A McGee-gráf karakterisztikus polinomja : .

A McGee-gráfcsoport automorfizmusának 32-es rendje van, és nem csúcstranzitív – két csúcspálya van, amelyek hossza 8 és 16. A McGee-gráf a legkisebb köbös cella, amely nem csúcstranzitív [9] .

Galéria

Jegyzetek

  1. ↑ Weisstein, Eric W. McGee Graph  a Wolfram MathWorld webhelyen .
  2. ↑ Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. ENSZ. Mat. ital. 15, 522-528, 1960
  3. ↑ McGee, WF "A hetes körméret minimális köbgrafikája." Kanada. Math. Bika. 3, 149-152, 1960
  4. ↑ Tutte, WT Connectivity in Graphs. Toronto, Ontario: University of Toronto Press, 1966
  5. ↑ Wong, PK "Cages--A Survey". J Th. 6, 1-22, 1982
  6. ↑ Brouwer, AE; Cohen, A. M.; és Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 209, 1989
  7. ↑ Pegg, E.T. és Exoo, G. „Crossing Number Graphs”. Mathematica J. 11, 2009
  8. ↑ Weisstein, Eric W. Graph Crossing Number  a Wolfram MathWorld webhelyén .
  9. ↑ Bondy, JA és Murty, USR Graph Theory with Applications. New York: North Holland, p. 237, 1976.