Robertson graf

Robertson-graf
Robertson-grafen är Hamiltonsk.
Döpt efter	Neil Robertson
Vertices	19
Kanter	38
Radie	3
Diameter	3
Omkrets	5
Automorfismer	24 ( D 12 )
Kromatiskt nummer	3
Kromatiskt index	5
Boktjocklek	3
Könummer	2
Egenskaper	Cage Hamiltonian
Tabell över grafer och parametrar

Inom det matematiska området för grafteori är Robertson -grafen eller (4,5)-buren en 4- regelbunden oriktad graf med 19 hörn och 38 kanter uppkallad efter Neil Robertson .

Robertson-grafen är den unika (4,5)-bur-grafen och upptäcktes av Robertson 1964. Som bur-graf är den den minsta 4-regelbundna grafen med omkrets 5.

Den har kromatiskt nummer 3, kromatiskt index 5, diameter 3, radie 3 och är både 4- vertex-ansluten och 4- kant-ansluten . Den har boktjocklek 3 och kö nummer 2.

Robertson-grafen är också en Hamilton-graf som har 5 376 distinkta riktade Hamilton-cykler.

Robertson-grafen är en av de minsta graferna med polis nummer 4.

Algebraiska egenskaper

Robertson-grafen är inte en vertextransitiv graf och dess fullständiga automorfismgrupp är isomorf till den dihedriska gruppen av ordning 24, gruppen av symmetrier för en vanlig tolvhörning , inklusive både rotationer och reflektioner.

Det karakteristiska polynomet i Robertson-grafen är

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

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

Galleri

• 

  Robertson-grafen som ritad i den ursprungliga publikationen.

• 

  Det kromatiska numret på Robertson-grafen är 3.

• 

  Det kromatiska indexet för Robertson-grafen är 5.