Conde de Herschel

En teoría de grafos, el gráfico de Herschel  es un gráfico bipartito no dirigido con 11 vértices y 18 aristas, el gráfico poliédrico no hamiltoniano más pequeño. El gráfico lleva el nombre del astrónomo británico A. S. Herschel , quien escribió un trabajo temprano sobre el juego Ikosian de William Rowan Hamilton  : el gráfico de Herschel da el poliedro convexo más pequeño para el que el juego no tiene solución. Sin embargo, el artículo de Herschel describe soluciones para el juego "Ikosian" solo para el tetraedro y el icosaedro , y no describe el gráfico de Herschel [1] .

Propiedades

El gráfico de Herschel es plano  : se puede dibujar en un plano sin cruzar los bordes. También está conectado con el vértice 3: al  eliminar dos vértices cualesquiera, el subgrafo queda conectado. Por tanto, según el teorema de Steinitz , el grafo de Goldner -Harari es un grafo poliédrico-  es un poliedro convexo ( eneaedro ) que tiene como esqueleto al grafo de Herschel [2] . El gráfico de Herschel también es bipartito  : sus vértices se pueden dividir en dos subconjuntos de cinco y seis vértices para que cada borde tenga puntos finales en ambos conjuntos (subconjuntos rojo y azul en la figura).

Como cualquier otro gráfico bipartito, el gráfico de Herschel es perfecto  : el número cromático de cualquier subgráfico generado es igual al tamaño de la camarilla más grande de este subgráfico. El gráfico tiene índice cromático 4, circunferencia 4, radio 3 y diámetro 4.

hamiltoniano

Dado que el gráfico es bipartito y tiene un número impar de vértices, no contiene un ciclo hamiltoniano (un ciclo de aristas que pasa por cada vértice exactamente una vez). En cualquier gráfico bipartito, cualquier ciclo debe pasar alternativamente por ambos conjuntos de vértices y, por lo tanto, debe contener el mismo número de vértices de ambos tipos y tener una longitud uniforme. Por tanto, no puede existir un ciclo que pase por cada uno de los once vértices. Un gráfico es un gráfico poliédrico mínimo no hamiltoniano, sin importar cómo se mida el tamaño del gráfico, por el número de vértices, aristas o caras [3] . Hay otro gráfico poliédrico con 11 vértices que no tiene ciclos hamiltonianos (a saber, el gráfico de Goldner-Harari [4] ), pero no hay ningún gráfico con menor (o igual) número de aristas [2] .

Todos los vértices del gráfico de Herschel, excepto tres, tienen grado tres. La conjetura de Tate [5] establece que un gráfico poliédrico en el que cualquier vértice tiene grado tres debe ser hamiltoniano, pero es refutado por el contraejemplo de Tutt , el gráfico mucho más grande de Tutt [6] . Una actualización de la conjetura de Tutt, la conjetura de Barnett de que cualquier gráfico poliédrico bipartito 3-regular es hamiltoniano, permanece abierta [7] .

El gráfico de Herschel también brinda un ejemplo de un gráfico poliédrico para el cual el gráfico central no se puede dividir en dos ciclos hamiltonianos que no se cruzan. El gráfico central del gráfico de Herschel es un gráfico regular de 4 con 18 vértices, uno para cada borde del gráfico de Herschel. Dos vértices son adyacentes en un gráfico de mediana si las aristas correspondientes del gráfico de Herschel van secuencialmente en una de sus caras [8] .

Propiedades algebraicas

El gráfico de Herschel no es de vértice transitivo y su grupo de automorfismo completo es isomorfo al grupo diédrico de orden 12 , el grupo de simetría de un hexágono regular , que incluye rotaciones y reflexiones. Cualquier permutación de sus vértices de cuarto grado se puede representar mediante un automorfismo gráfico, y también existe un automorfismo no trivial que permuta los vértices restantes sin afectar a los vértices de cuarto grado.

El polinomio característico del gráfico de Herschel es .

Notas

1. ↑ AS Herschel. Señor Wm. El juego icosiano de Hamilton  // The Quarterly Journal of Pure and Applied Mathematics . - 1862. - T. 5 . - art. 305 .
2. ↑ 1 2 H. S. M. Coxeter. Politopos regulares . - Dover, 1973. - Pág  . 8 .
3. ↑ David Barnette, Ernest Jucovic. Circuitos hamiltonianos en 3 politopos // Journal of Combinatorial Theory. - 1970. - T. 9 , núm. 1 . - S. 54-59 . - doi : 10.1016/S0021-9800(70)80054-0 .
4. ↑ Weisstein, Eric W. Goldner-Harary Gráfico  en el sitio web Wolfram MathWorld .
5. ↑ PG Tait. Topología del Listado  // Revista Filosófica (5ª ser.). - 1884. - T. 17 . - S. 30-46 . . Reimpreso en Scientific Papers , vol. II, págs. 85-98.
6. ↑ WT Tutte. En circuitos hamiltonianos  // Revista de la Sociedad Matemática de Londres. - 1946. - T. 21 , núm. 2 . - S. 98-101 . -doi : 10.1112 / jlms/s1-21.2.98 .
7. ↑ Roberto Samal. Conjetura de Barnette . — The Open Problem Garden, 11 de junio de 2007.
8. ↑ JA Bondy, R. Häggkvist. Ciclos de Hamilton disjuntos por aristas en grafos planos regulares de 4 // Aequationes Mathematicae. - 1981. - T. 22 , núm. 1 . - S. 42-45 . -doi : 10.1007/ BF02190157 .

Enlaces

• Weisstein, Eric W. Herschel Graph  (inglés) en el sitio web de Wolfram MathWorld .