Contele McGee
| Contele McGee | |
|---|---|
| Numit după | WF McGee |
| Vârfurile | 24 |
| coaste | 36 |
| Rază | patru |
| Diametru | patru |
| Circumferinţă | 7 |
| Automorfisme | 32 |
| Număr cromatic | 3 |
| Indicele cromatic | 3 |
| Proprietăți |
celulă cubică hamiltoniană |
| Fișiere media la Wikimedia Commons | |
În teoria grafurilor, un grafic McGee sau celula (3-7) este un graf regulat cu 24 de vârfuri și 36 de muchii. [unu]
Graph McGee este singura celulă (3,7) ( cel mai mic cubic cu circumferința 7). Este cea mai mică celulă cubică non- Moore graph .
Descoperit prima dată de Horst Sachs, dar nepublicat [2] , graficul poartă numele lui McGee ( WF McGee ), care a publicat rezultatul în 1960 [3] . Mai târziu, în 1966 , William Thomas Tutt a demonstrat că aceasta este singura celulă (3,7) [4] [5] [6] .
Sunt cunoscute cele mai mici grafice cubice cu 1–8 încrucișări (secvența A110507 în OEIS ), cel mai mic grafic cu 8 încrucișări este graficul McGee. Există 5 grafice cubice neizomorfe de ordinul 24 cu 8 încrucișări [7] , unul dintre ele este graficul Petersen generalizat G (12,5), cunoscut și sub numele de Graficul Nauru [8] .
Graficul McGee are o rază de 4, un diametru de 4, un număr cromatic de 3 și un indice cromatic de 3. De asemenea, este conectat la 3 vârfuri și la 3 muchii .
Proprietăți algebrice
Polinomul caracteristic al graficului McGee este .
Automorfismul grupului de graf McGee are ordinul 32 și nu este tranzitiv la vârf — există două orbite de vârf cu lungimea 8 și 16. Graficul McGee este cea mai mică celulă cubică care nu este tranzitivă la vârf [9] .
Galerie
-
Numărul de intersecții ale graficului McGee este 8.
-
Numărul cromatic al Contelui McGee este 3.
-
Indicele cromatic al Contelui McGee este 3.
-
Indicele cromatic aciclic al graficului McGee este 3.
-
Reprezentare alternativă a Contelui McGee.
Note
- ^ Weisstein , Eric W. McGee Graph pe site- ul Wolfram MathWorld .
- ↑ Kárteszi, F. „Piani finit ciclici come risoluzioni di un certo problemo di minimo”. Boll. Un. Mat. ital. 15, 522-528, 1960
- ↑ McGee, WF „A Minimal Cubic Graph of Girth Seven”. Canada. Matematică. Taur. 3, 149-152, 1960
- ↑ Tutte, WT Connectivity in Graphs. Toronto, Ontario: University of Toronto Press, 1966
- ↑ Wong, PK „Cages--A Survey”. J Graficul Th. 6, 1-22, 1982
- ↑ Brouwer, AE; Cohen, A. M.; și Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 209, 1989
- ↑ Pegg, E.T. și Exoo, G. „Crossing Number Graphs”. Mathematica J. 11, 2009
- ^ Weisstein , Eric W. Graph Crossing Number pe site- ul Wolfram MathWorld .
- ↑ Bondy, JA și Murty, USR Graph Theory with Applications. New York: Olanda de Nord, p. 237, 1976.