Robertsonův graf - Robertson graph

Robertsonův graf
Robertsonův graf hamiltonian.svg
Robertsonův graf je hamiltoniánský.
Pojmenoval podleNeil Robertson
Vrcholy19
Hrany38
Poloměr3
Průměr3
Obvod5
Automorfismy24 (D12 )
Chromatické číslo3
Chromatický index5[1]
Tloušťka knihy3
Číslo fronty2
VlastnostiKlec
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

Reference

  1. ^ Weisstein, Eric W. „Class 2 Graph“. MathWorld.
  2. ^ Weisstein, Eric W. „Robertsonův graf“. MathWorld.
  3. ^ Bondy, J. A. a Murty, U. S. R. Teorie grafů s aplikacemi. New York: Severní Holandsko, str. 237, 1976.
  4. ^ Robertson, N. "Nejmenší graf obvodu 5 a valence 4." Býk. Amer. Matematika. Soc. 70, 824-825, 1964.
  5. ^ Jessica Wolz, Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
  6. ^ Geoffrey Exoo a Robert Jajcay, průzkum dynamické klece, Electr. J. Combin. 15, 2008.