McGeeův graf - McGee graph

McGeeův graf
	McGeeův graf
Pojmenoval podle	W. F. McGee
Vrcholy	24
Hrany	36
Poloměr	4
Průměr	4
Obvod	7
Automorfismy	32
Chromatické číslo	3
Chromatický index	3
Tloušťka knihy	3
Číslo fronty	2
Vlastnosti	Krychlový; Klec; Hamiltonian
	Tabulka grafů a parametrů

V matematický pole teorie grafů, McGeeův graf nebo (3-7) klec je 3-běžný graf s 24 vrcholy a 36 hranami.^[1]

McGeeův graf je jedinečný (3,7) -klec (nejmenší kubický graf obvodu 7). Je to také nejmenší kubická klec, která není a Mooreův graf.

Poprvé objevena Sachsovou, ale nepublikovaná,^[2] graf je pojmenován po McGeeovi, který publikoval výsledek v roce 1960.^[3] Poté byl v roce 1966 Tutte McGee graf prokázán jako jedinečná (3,7) klec.^[4]^[5]^[6]

McGeeův graf vyžaduje alespoň osm křížení při jakémkoli jeho vykreslení v rovině. Je to jeden z pěti neizomorfních grafů, které jsou svázány jako nejmenší kubický graf, který vyžaduje osm křížení. Dalším z těchto pěti grafů je zobecněný Petersenův graf G(12,5), také známý jako Nauru graf.^[7]^[8]

McGeeův graf má poloměr 4, průměr 4, chromatické číslo 3 a chromatický index 3. Je to také 3-připojen k vrcholu a 3-připojeno k okraji graf. Má to tloušťka knihy 3 a číslo fronty 2.^[9]

Algebraické vlastnosti

The charakteristický polynom McGeeho grafu je

{displaystyle x ^ {3} (x-3) (x-2) ^ {3} (x + 1) ^ {2} (x + 2) (x ^ {2} + x-4) (x ^ { 3} + x ^ {2} -4x-2) ^ {4}}

.

Skupina automorfismu McGeeho grafu je řádu 32 a na jeho vrcholy nepůsobí přechodně: existují dvě vrcholové dráhy o délkách 8 a 16. McGeeův graf je nejmenší kubická klec, která není vrchol-tranzitivní graf.^[10]^{[je zapotřebí lepší zdroj ]}

Galerie

The číslo křížení McGeeho grafu je 8.
The chromatické číslo McGeeho grafu je 3.
The chromatický index McGeeho grafu je 3.
The acyklické chromatické číslo McGeeho grafu je 3.
Alternativní kresba McGeeho grafu.

Reference

^ ^A ^b ^C ^d ^E ^F Weisstein, Eric W. „McGee Graph“. MathWorld.
^ Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. Un. Rohož. Ital. 15, 522-528, 1960
^ McGee, W. F. „Minimální kubický graf sedmého obvodu.“ Canad. Matematika. Býk. 3, 149-152, 1960
^ Tutte, W. T. Připojení v grafech. Toronto, Ontario: University of Toronto Press, 1966
^ Wong, P. K. „Klece - průzkum.“ J. Graph Th. 6, 1-22, 1982
^ Brouwer, A.E .; Cohen, A. M .; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, str. 209, 1989
^ Sloane, N. J. A. (vyd.). "Posloupnost A110507 (počet uzlů v nejmenším kubickém grafu s křížením číslo n)". The On-line encyklopedie celočíselných sekvencí. Nadace OEIS.
^ Pegg, E. T.; Exoo, G. (2009), „Crossing number graphs“, Mathematica Journal, 11.
^ Jessica Wolz, Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
^ Bondy, J. A. a Murty, U. S. R. Teorie grafů s aplikacemi. New York: Severní Holandsko, str. 237, 1976.

[Mathworld-1] A ^b ^C ^d ^E ^F Weisstein, Eric W. „McGee Graph“. MathWorld.

[2] Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. Un. Rohož. Ital. 15, 522-528, 1960

[3] McGee, W. F. „Minimální kubický graf sedmého obvodu.“ Canad. Matematika. Býk. 3, 149-152, 1960

[4] Tutte, W. T. Připojení v grafech. Toronto, Ontario: University of Toronto Press, 1966

[5] Wong, P. K. „Klece - průzkum.“ J. Graph Th. 6, 1-22, 1982

[6] Brouwer, A.E .; Cohen, A. M .; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, str. 209, 1989

[7] Sloane, N. J. A. (vyd.). "Posloupnost A110507 (počet uzlů v nejmenším kubickém grafu s křížením číslo n)". The On-line encyklopedie celočíselných sekvencí. Nadace OEIS.

[8] Pegg, E. T.; Exoo, G. (2009), „Crossing number graphs“, Mathematica Journal, 11.

[9] Jessica Wolz, Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018

[10] Bondy, J. A. a Murty, U. S. R. Teorie grafů s aplikacemi. New York: Severní Holandsko, str. 237, 1976.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]