Meredith graf

Meredith-graf
Meredith-grafen
Döpt efter	GH Meredith
Vertices	70
Kanter	140
Radie	7
Diameter	8
Omkrets	4
Automorfismer	38698352640
Kromatiskt nummer	3
Kromatiskt index	5
Boktjocklek	3
Könummer	2
Egenskaper	Eulerian
Tabell över grafer och parametrar

Inom det matematiska området grafteori är Meredith-grafen en 4- regelbunden oriktad graf med 70 hörn och 140 kanter som upptäcktes av Guy HJ Meredith 1973.

Meredith-grafen är 4- vertex-ansluten och 4- kant-ansluten , har kromatiskt nummer 3, kromatiskt index 5, radie 7, diameter 8, omkrets 4 och är icke-hamiltonsk . Den har boktjocklek 3 och kö nummer 2.

Publicerad 1973 ger den ett motexempel till Crispin Nash-Williams gissning att varje 4-regelbunden 4-vertex-kopplad graf är Hamiltonsk. WT Tutte visade dock att alla 4-kopplade plana grafer är hamiltoniska.

Det karakteristiska polynomet i Meredith-grafen är $(x-4)(x-1)^{10}x^{21}(x+1)^{11}(x+3)(x^{ 2}-13)(x^{6}-26x^{4}+3x^{3}+169x^{2}-39x-45)^{4}$ .

Galleri

• 

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

• 

  Meredith-grafens kromatiska index är 5 .