Greve McGee
| Greve McGee | |
|---|---|
| Döpt efter | WF McGee |
| Toppar | 24 |
| revben | 36 |
| Radie | fyra |
| Diameter | fyra |
| Omkrets | 7 |
| Automorfismer | 32 |
| Kromatiskt nummer | 3 |
| Kromatiskt index | 3 |
| Egenskaper |
kubisk hamiltonisk cell |
| Mediafiler på Wikimedia Commons | |
I grafteorin är en McGee-graf , eller (3-7)-cell , en 3 - regelbunden graf med 24 hörn och 36 kanter. [ett]
Graf McGee är den enda (3,7) -cellen (minsta kubik med omkrets 7). Det är den minsta kubiska cellen av icke - Moore graf .
Först upptäckt av Horst Sachs, men inte publicerad [2] , grafen är uppkallad efter McGee ( WF McGee ), som publicerade resultatet 1960 [3] . Senare, 1966 , bevisade William Thomas Tutt att detta är den enda (3,7)-cellen [4] [5] [6] .
De minsta kubikgraferna med 1–8 korsningar är kända (sekvens A110507 i OEIS ), den minsta grafen med 8 korsningar är McGee-grafen. Det finns 5 nonisomorfa kubiska grafer av ordning 24 med 8 korsningar [7] , en av dem är den generaliserade Petersen-grafen G (12,5), även känd som Nauru-grafen [8] .
McGee-grafen har en radie på 4, en diameter på 4, ett kromatiskt tal på 3 och ett kromatiskt index på 3. Den är också 3 -vertex-ansluten och 3 -kant-ansluten .
Algebraiska egenskaper
Det karakteristiska polynomet i McGee-grafen är .
McGee-grafgruppens automorfism har ordning 32 och är inte vertextransitiv – det finns två vertexbanor med längden 8 och 16. McGee-grafen är den minsta kubiska cellen som inte är vertextransitiv [9] .
Galleri
-
Antalet skärningspunkter i McGee-grafen är 8.
-
Det kromatiska talet för greve McGee är 3.
-
Greve McGees kromatiska index är 3.
-
McGee-grafens acykliska kromatiska index är 3 .
-
Alternativ skildring av greve McGee.
Anteckningar
- ↑ Weisstein, Eric W. McGee Graph på Wolfram MathWorld- webbplatsen .
- ↑ Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. Fn. Matta. ital. 15, 522-528, 1960
- ↑ McGee, WF "A Minimal Cubic Graph of Girth Seven." Kanada. Matematik. Tjur. 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.; och Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, sid. 209, 1989
- ↑ Pegg, E.T. och Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009
- ↑ Weisstein, Eric W. Graph Crossing Number på Wolfram MathWorld- webbplatsen .
- ↑ Bondy, JA och Murty, USR Grafteori med tillämpningar. New York: North Holland, sid. 237, 1976.