Grev McGee
| Grev McGee | |
|---|---|
| Opkaldt efter | WF McGee |
| Toppe | 24 |
| ribben | 36 |
| Radius | fire |
| Diameter | fire |
| Omkreds | 7 |
| Automorfismer | 32 |
| Kromatisk tal | 3 |
| Kromatisk indeks | 3 |
| Ejendomme |
kubisk hamiltonsk celle |
| Mediefiler på Wikimedia Commons | |
I grafteori er en McGee-graf eller (3-7)-celle en 3 - regulær graf med 24 hjørner og 36 kanter. [en]
Graf McGee er den eneste (3,7) -celle (mindste kubisk med omkreds 7). Det er den mindste ikke - Moore graf kubiske celle .
Først opdaget af Horst Sachs, men ikke offentliggjort [2] , er grafen opkaldt efter McGee ( WF McGee ), som offentliggjorde resultatet i 1960 [3] . Senere, i 1966 , beviste William Thomas Tutt , at dette er den eneste (3,7)-celle [4] [5] [6] .
De mindste kubiske grafer med 1-8 krydsninger er kendt (sekvens A110507 i OEIS ), den mindste graf med 8 krydsninger er McGee grafen. Der er 5 ikke-isomorfe kubiske grafer af størrelsesorden 24 med 8 krydsninger [7] , en af dem er den generaliserede Petersen-graf G (12,5), også kendt som Nauru-grafen [8] .
McGee-grafen har en radius på 4, en diameter på 4, et kromatisk tal på 3 og et kromatisk indeks på 3. Den er også 3 -vertex-forbundet og 3 -kant -forbundet .
Algebraiske egenskaber
McGee-grafens karakteristiske polynomium er .
McGee-grafgruppens automorfi har orden 32 og er ikke vertex-transitiv - der er to toppunkter med længden 8 og 16. McGee-grafen er den mindste kubiske celle, der ikke er toppunkttransitiv [9] .
Galleri
-
Antallet af skæringspunkter i McGee-grafen er 8.
-
Grev McGees kromatiske indeks er 3.
-
McGee-grafens acykliske kromatiske indeks er 3 .
-
Alternativ afbildning af grev McGee.
Noter
- ↑ Weisstein, Eric W. McGee Graph på Wolfram MathWorld- webstedet .
- ↑ Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. Un. Måtte. ital. 15, 522-528, 1960
- ↑ McGee, WF "A Minimal Cubic Graph of Girth Seven." Canada. Matematik. Tyr. 3, 149-152, 1960
- ↑ Tutte, WT Connectivity in Graphs. Toronto, Ontario: University of Toronto Press, 1966
- ↑ Wong, PK "Cages--A Survey." J Graf Th. 6, 1-22, 1982
- ↑ Brouwer, AE; Cohen, A.M.; og Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, s. 209, 1989
- ↑ Pegg, E.T. og Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009
- ↑ Weisstein, Eric W. Graph Crossing Number på Wolfram MathWorld- webstedet .
- ↑ Bondy, JA og Murty, USR Graph Theory with Applications. New York: Nordholland, s. 237, 1976.