Robertsonův graf - Robertson graph
Robertsonův graf | |
---|---|
![]() Robertsonův graf je hamiltoniánský. | |
Pojmenoval podle | Neil Robertson |
Vrcholy | 19 |
Hrany | 38 |
Poloměr | 3 |
Průměr | 3 |
Obvod | 5 |
Automorfismy | 24 (D12 ) |
Chromatické číslo | 3 |
Chromatický index | 5[1] |
Tloušťka knihy | 3 |
Číslo fronty | 2 |
Vlastnosti | Klec Hamiltonian |
Tabulka grafů a parametrů |
V matematický pole teorie grafů, Robertsonův graf nebo (4,5) klec, je 4-pravidelný neorientovaný graf s 19 vrcholy a 38 hranami pojmenovanými podle Neil Robertson.[2][3]
Robertsonův graf je jedinečný (4,5) -klec graf a byl objeven Robertsonem v roce 1964.[4] Jako klecový graf je to nejmenší 4-pravidelný graf s obvodem 5.
Má to chromatické číslo 3, chromatický index 5, průměr 3, poloměr 3 a oba jsou 4připojen k vrcholu a 4-připojeno k okraji. Má to tloušťka knihy 3 a číslo fronty 2.[5]
Robertsonův graf je také a Hamiltonovský graf který má 5 376 odlišných směrovaných hamiltonovských cyklů.
Algebraické vlastnosti
Robertsonův graf není vrchol-tranzitivní graf a jeho úplná skupina automorfismu je izomorfní s dihedrální skupina řádu 24, skupina symetrií pravidelného dodekagon, včetně rotací i odrazů.[6]
The charakteristický polynom Robertsonova grafu je
Galerie
Robertsonův graf nakreslený v původní publikaci.
The chromatické číslo Robertsonova grafu je 3.
The chromatický index Robertsonova grafu je 5.
Reference
- ^ Weisstein, Eric W. „Class 2 Graph“. MathWorld.
- ^ Weisstein, Eric W. „Robertsonův graf“. MathWorld.
- ^ Bondy, J. A. a Murty, U. S. R. Teorie grafů s aplikacemi. New York: Severní Holandsko, str. 237, 1976.
- ^ Robertson, N. "Nejmenší graf obvodu 5 a valence 4." Býk. Amer. Matematika. Soc. 70, 824-825, 1964.
- ^ Jessica Wolz, Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
- ^ Geoffrey Exoo a Robert Jajcay, průzkum dynamické klece, Electr. J. Combin. 15, 2008.