Gráfico de Franklin

Gráfico de Franklin
El gráfico de Franklin
Lleva el nombre de	Philip Franklin
Vértices	12
Bordes	18
Radio	3
Diámetro	3
Circunferencia	4
Automorfismos	48 ( Z / 2 Z × S ₄ )
Número cromático	2
Índice cromático	3
Género	1
Propiedades	Cúbico hamiltoniano bipartito sin triángulo perfecto vértice transitivo
Tabla de gráficos y parámetros

En el campo matemático de la teoría de grafos , el grafo de Franklin es un grafo 3 regular con 12 vértices y 18 aristas.

El gráfico de Franklin lleva el nombre de Philip Franklin , quien refutó la conjetura de Heawood sobre el número de colores necesarios cuando una superficie bidimensional se divide en celdas mediante una incrustación de gráfico . ^[1] La conjetura de Heawood implicaba que el número cromático máximo de un mapa en la botella de Klein debería ser siete, pero Franklin demostró que en este caso seis colores siempre son suficientes. (La botella de Klein es la única superficie en la que falla la conjetura de Heawood.) El gráfico de Franklin se puede incrustar en la botella de Klein para que forme un mapa que requiera seis colores, mostrando que a veces se necesitan seis colores en este caso. Esta incrustación es el dual Petrie de su incrustación en elplano proyectivo que se muestra a continuación.

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 de 3 vértices conectados y 3 bordes conectados .

Propiedades algebraicas

El grupo de automorfismo del gráfico de Franklin es de orden 48 y es isomorfo a Z / 2 Z × S ₄ , el producto directo del grupo cíclico Z / 2 Z y el grupo simétrico S ₄ . Actúa transitivamente en los vértices de la gráfica, por lo que es vértice-transitivo .

El polinomio característico del gráfico de Franklin es

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

Galería

El número cromático del gráfico de Franklin es 2.
El índice cromático del gráfico de Franklin es 3.
Dibujo alternativo del gráfico de Franklin.
El gráfico de Franklin incrustado en el plano proyectivo como el hemi-octaedro truncado .

Wikimedia Commons tiene medios relacionados con el gráfico de Franklin .

Referencias

^ Franklin, P. "Un problema de seis colores". J. Math. Phys. 13, 363-379, 1934. doi : 10.1002 / sapm1934131363

[1] Franklin, P. "Un problema de seis colores". J. Math. Phys. 13, 363-379, 1934. doi : 10.1002 / sapm1934131363

[1]