Conde de Franklin
| Conde de Franklin | |
|---|---|
| Lleva el nombre de | franklin |
| picos | 12 |
| costillas | Dieciocho |
| Radio | 3 |
| Diámetro | 3 |
| Circunferencia | cuatro |
| automorfismos | 48 ( Z / 2 Z × S 4 ) |
| Número cromático | 2 |
| índice cromático | 3 |
| Género | una |
| Propiedades |
Cúbico Hamiltoniano Bipartito Sin triángulos Perfecto Transitivo de vértice |
| Archivos multimedia en Wikimedia Commons | |
En la teoría de grafos, un grafo de Franklin es un grafo regular de 3 con 12 vértices y 18 aristas [1] .
El gráfico lleva el nombre de Philip Franklin , quien refutó la conjetura de Heawood sobre la cantidad de colores necesarios para colorear superficies bidimensionales divididas en celdas cuando el gráfico está incrustado [2] [3] . Según la conjetura de Heawood, el número cromático máximo de un mapa en una botella de Klein debería ser siete, pero Franklin demostró que seis colores siempre son suficientes para un gráfico dado. El gráfico de Franklin se puede incrustar en una botella de Klein para que forme una tarjeta que requiera seis colores, lo que muestra que en algunos casos seis colores son suficientes. Esta incrustación es el dual de Petri de la incrustación en el plano proyectivo (la incrustación se muestra a continuación).
El gráfico es hamiltoniano y tiene número cromático 2, índice cromático 3, radio 3, diámetro 3 y circunferencia 4. También es un gráfico perfecto conectado por 3 vértices y 3 aristas .
Propiedades algebraicas
El grupo de automorfismos del grafo de Franklin tiene orden 48 y es isomorfo a Z /2 Z × S 4 , el producto directo del grupo cíclico Z /2 Z y el grupo simétrico S 4 . El grupo actúa transitivamente sobre los vértices del grafo.
El polinomio característico del gráfico de Franklin es
Galería
-
El número cromático del Conde Franklin es 2.
-
El índice cromático del Conde Franklin es 3.
-
Dibujo alternativo del Conde Franklin.
-
El gráfico de Franklin incrustado en el plano proyectivo como un semi-octaedro truncado .
Notas
- ↑ Weisstein, Eric W. Franklin Graph en el sitio web de Wolfram MathWorld .
- ↑ Conjetura de Weisstein, Eric W. Heawood en el sitio web Wolfram MathWorld .
- ↑ Franklin, 1934 , pág. 363-379.
Literatura
- P.Franklin. Un problema de seis colores // J. Math. Phys.. - 1934. - T. 13 . - S. 363-379 .