Earl av Franklin

Earl av Franklin
Döpt efter Franklin
Toppar 12
revben arton
Radie 3
Diameter 3
Omkrets fyra
Automorfismer 48 ( Z /2 Z × S 4 )
Kromatiskt nummer 2
Kromatiskt index 3
Släkte ett
Egenskaper Kubisk
Hamiltonsk
tvådelad
Inga trianglar
Perfekt
Vertex-transitiv
 Mediafiler på Wikimedia Commons

I grafteorin är en Franklin-graf  en 3- regelbunden graf med 12 hörn och 18 kanter [1] .

Grafen är uppkallad efter Philip Franklin , som tillbakavisade Heawoods gissning om antalet färger som behövs för att färga tvådimensionella ytor uppdelade i celler när grafen är inbäddad [2] [3] . Enligt Heawoods gissning borde det maximala kromatiska antalet av en karta på en Klein-flaska vara sju, men Franklin bevisade att sex färger alltid räcker för en given graf. Franklin-grafen kan bäddas in i en Klein-flaska så att den bildar ett kort som kräver sex färger, vilket visar att i vissa fall räcker sex färger. Denna inbäddning är Petri-dualen av inbäddningen i det projektiva planet (inbäddningen visas nedan).

Grafen är Hamiltonsk och har kromatiskt nummer 2, kromatiskt index 3, radie 3, diameter 3 och omkrets 4. Det är också en 3-vertex-ansluten och 3-kant-ansluten perfekt graf .

Algebraiska egenskaper

Automorfismgruppen i Franklin-grafen har ordningen 48 och är isomorf till Z /2 Z × S 4 , den direkta produkten av den cykliska gruppen Z /2 Z och den symmetriska gruppen S 4 . Gruppen agerar transitivt på grafens hörn.

Det karakteristiska polynomet i Franklin-grafen är

Galleri

Anteckningar

  1. ↑ Weisstein, Eric W. Franklin Graph  på Wolfram MathWorld- webbplatsen .
  2. ↑ Weisstein, Eric W. Heawood gissningar  på Wolfram MathWorld- webbplatsen .
  3. ↑ Franklin, 1934 , sid. 363-379.

Litteratur