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

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

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

Galerie

• 

  Robertsonův graf nakreslený v původní publikaci.

• 

  The chromatické číslo Robertsonova grafu je 3.

• 

  The chromatický index Robertsonova grafu je 5.

Reference