Franklinův graf - Franklin graph - Wikipedia

Franklinův graf
Franklinův graf
Pojmenoval podle	Philip Franklin
Vrcholy	12
Hrany	18
Poloměr	3
Průměr	3
Obvod	4
Automorfismy	48 (Z/2Z ×S4 )
Chromatické číslo	2
Chromatický index	3
Rod	1
Vlastnosti	Krychlový Hamiltonian Bipartitní Bez trojúhelníků Perfektní Vrchol-tranzitivní
Tabulka grafů a parametrů

V matematický pole teorie grafů, Franklinův graf je 3-běžný graf s 12 vrcholy a 18 hranami.^[1]

Franklinův graf je pojmenován po Philip Franklin, který vyvrátil Heawood dohad na počtu potřebných barev, když je dvojrozměrný povrch rozdělen na buňky pomocí a vkládání grafů.^[2][3] Z domněnky Heawood vyplývá, že maximální chromatický počet map na mapě Kleinova láhev by mělo být sedm, ale Franklin dokázal, že v tomto případě vždy stačí šest barev. Franklinův graf může být vložen do Kleinovy ​​láhve tak, že tvoří mapu vyžadující šest barev, což ukazuje, že v tomto případě je někdy potřeba šest barev. Toto vložení je Petrie dual jeho vložení do projektivní rovina je uvedeno níže.

to je Hamiltonian a má chromatické číslo 2, chromatický index 3, poloměr 3, průměr 3 a obvod 4. Je to také 3-připojen k vrcholu a 3-připojeno k okraji perfektní graf.

Algebraické vlastnosti

The automorfická skupina Franklinova grafu je řádu 48 a je izomorfní s Z/2Z×S₄, přímý produkt z cyklická skupina Z/2Z a symetrická skupina S₄. Působí přechodně na vrcholy grafu, čímž se stává vrchol-tranzitivní.

The charakteristický polynom Franklinova grafu je

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

Galerie

• 

  The chromatické číslo Franklinova grafu je 2.

• 

  The chromatický index Franklinova grafu je 3.

• 

  Alternativní kresba Franklinova grafu.

• 

  Franklinův graf vložený do projektivní roviny jako zkrácen hemi-oktaedron.

Reference