Jarl af Franklin
| Jarl af Franklin | |
|---|---|
| Opkaldt efter | Franklin |
| Toppe | 12 |
| ribben | atten |
| Radius | 3 |
| Diameter | 3 |
| Omkreds | fire |
| Automorfismer | 48 ( Z /2 Z × S 4 ) |
| Kromatisk tal | 2 |
| Kromatisk indeks | 3 |
| Slægt | en |
| Ejendomme |
Kubisk Hamiltonsk Bipartite Ingen trekanter Perfekt Vertex-transitiv |
| Mediefiler på Wikimedia Commons | |
I grafteori er en Franklin-graf en 3 -regulær graf med 12 hjørner og 18 kanter [1] .
Grafen er opkaldt efter Philip Franklin , som tilbageviste Heawoods formodning om antallet af farver, der skal til for at farve todimensionelle overflader opdelt i celler, når grafen er indlejret [2] [3] . Ifølge Heawoods formodning skulle det maksimale kromatiske antal af et kort på en Klein-flaske være syv, men Franklin beviste, at seks farver altid er tilstrækkelige til en given graf. Franklin-grafen kan indlejres i en Klein-flaske, så den danner et kort, der kræver seks farver, hvilket viser, at i nogle tilfælde er seks farver tilstrækkeligt. Denne indlejring er Petri-dualen af indlejringen i det projektive plan (indlejring vist nedenfor).
Grafen er Hamiltonsk og har kromatisk nummer 2, kromatisk indeks 3, radius 3, diameter 3 og omkreds 4. Det er også en 3-kant-forbundet og 3-kant-forbundet perfekt graf .
Algebraiske egenskaber
Automorfigruppen i Franklin-grafen har orden 48 og er isomorf til Z /2 Z × S 4 , det direkte produkt af den cykliske gruppe Z /2 Z og den symmetriske gruppe S 4 . Gruppen virker transitivt på grafens hjørner.
Franklin-grafens karakteristiske polynomium er
Galleri
-
Alternativ tegning af grev Franklin.
-
Franklin-grafen indlejret i det projektive plan som et afkortet semi-oktaeder .
Noter
- ↑ Weisstein, Eric W. Franklin Graph på Wolfram MathWorld- webstedet .
- ↑ Weisstein, Eric W. Heawood formodning på Wolfram MathWorld -webstedet .
- ↑ Franklin, 1934 , s. 363-379.
Litteratur
- P. Franklin. Et seksfarvet problem // J. Math. Phys.. - 1934. - T. 13 . - S. 363-379 .