Hrabě McGee
| Hrabě McGee | |
|---|---|
| Pojmenoval podle | WF McGee |
| Vrcholy | 24 |
| žebra | 36 |
| Poloměr | čtyři |
| Průměr | čtyři |
| obvod | 7 |
| Automorfismy | 32 |
| Chromatické číslo | 3 |
| Chromatický index | 3 |
| Vlastnosti |
кубический клетка гамильтонов |
| Mediální soubory na Wikimedia Commons | |
V teorii grafů je McGeeův graf neboli (3-7)-buňka 3 - běžný graf s 24 vrcholy a 36 hranami. [jeden]
Graph McGee je jediná (3,7) buňka (nejmenší krychlový obvod s obvodem 7). Jedná se o nejmenší krychlovou buňku bez Moorova grafu .
Poprvé objevil Horst Sachs, ale nezveřejněno [2] , graf je pojmenován po McGee ( WF McGee ), který výsledek zveřejnil v roce 1960 [3] . Později, v roce 1966 , William Thomas Tutt dokázal, že se jedná o jedinou (3,7)-buňku [4] [5] [6] .
Nejmenší kubické grafy s 1–8 kříženími jsou známy (sekvence A110507 v OEIS ), nejmenší graf s 8 kříženími je McGeeův graf. Existuje 5 neizomorfních kubických grafů řádu 24 s 8 kříženími [7] , jedním z nich je zobecněný Petersenův graf G (12,5), známý také jako Nauruův graf [8] .
McGeeův graf má poloměr 4, průměr 4, chromatické číslo 3 a chromatický index 3. Je také 3 -vertex-connected a 3 -edge-connected .
Algebraické vlastnosti
Charakteristickým polynomem McGeeova grafu je .
Autorphismus skupiny Graf McGi má řád 32 a není tranzitivní vzhledem k vrcholům - existují dvě orbity vrcholů délky 8 a 16. McGoy Count je nejmenší krychlová buňka, která není vertikální a tranzit [9] .
Galerie
-
Počet průsečíků McGee grafu je 8.
-
Chromatické číslo McGoy Count je 3.
-
Chromatický index Count McGi Racked 3.
-
Acyklický chromatický index McGee grafu je 3.
-
Alternativní zobrazení hraběte McGee.
Poznámky
- ↑ Weisstein, Eric W. McGee Graph na webu Wolfram MathWorld .
- ↑ Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. Un. Rohož. ital. 15, 522-528, 1960
- ↑ McGee, WF "Minimální kubický graf obvodu sedm." Kanada. Matematika. Býk. 3, 149-152, 1960
- ↑ Tutte, WT Konektivita v grafech. Toronto, Ontario: University of Toronto Press, 1966
- ↑ Wong, PK "Cages--A Survey." J Graf Th. 6, 1-22, 1982
- ↑ Brouwer, AE; Cohen, A. M.; a Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, s. 209, 1989
- ↑ Pegg, E.T. a Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009
- ↑ Weisstein, Eric W. Graph Crossing Number na webu Wolfram MathWorld .
- ↑ Bondy, JA a Murty, USR Graph Theory with Applications. New York: Severní Holandsko, s. 237, 1976.