En el campo matemático de la teoría de grafos , el grafo de Tutte es un grafo 3- regular con 46 vértices y 69 aristas que llevan el nombre de WT Tutte . [1] Tiene número cromático 3, índice cromático 3, circunferencia 4 y diámetro 8.
Gráfico de Tutte | |
---|---|
Lleva el nombre de | WT Tutte |
Vértices | 46 |
Bordes | 69 |
Radio | 5 |
Diámetro | 8 |
Circunferencia | 4 |
Automorfismos | 3 ( Z / 3 Z ) |
Número cromático | 3 |
Índice cromático | 3 |
Propiedades | Poliédrico plano cúbico |
Tabla de gráficos y parámetros |
El gráfico de Tutte es un gráfico poliédrico cúbico , pero no es hamiltoniano . Por lo tanto, es un contraejemplo de la conjetura de Tait de que cada poliedro de tres regulares tiene un ciclo hamiltoniano. [2]
Publicado por Tutte en 1946, es el primer contraejemplo construido para esta conjetura. [3] Más tarde se encontraron otros contraejemplos, en muchos casos basados en el teorema de Grinberg .
Construcción
A partir de un pequeño gráfico plano llamado fragmento de Tutte, WT Tutte construyó un poliedro no hamiltoniano, juntando tres de esos fragmentos. Los bordes "obligatorios" de los fragmentos, que deben ser parte de cualquier camino hamiltoniano a través del fragmento, están conectados en el vértice central; debido a que cualquier ciclo puede usar solo dos de estos tres bordes, no puede haber un ciclo hamiltoniano.
El gráfico resultante tiene 3 conexiones y es plano , por lo que, según el teorema de Steinitz , es el gráfico de un poliedro. Tiene 25 caras.
Se puede realizar geométricamente a partir de un tetraedro (cuyas caras corresponden a las cuatro grandes caras de nueve lados del dibujo, tres de las cuales están entre pares de fragmentos y la cuarta forma el exterior) truncando por multiplicación tres de sus vértices. .
Propiedades algebraicas
El grupo de automorfismo del gráfico de Tutte es Z / 3 Z , el grupo cíclico de orden 3.
El polinomio característico del gráfico de Tutte es:
Gráficos relacionados
Aunque el gráfico de Tutte es el primer gráfico poliédrico no hamiltoniano de 3 regulares que se descubre, no es el gráfico más pequeño de este tipo.
En 1965, Lederberg encontró el gráfico de Barnette-Bosák-Lederberg en 38 vértices. [4] [5] En 1968, Grinberg construyó pequeños contraejemplos adicionales a la conjetura de Tait: los gráficos de Grinberg en los vértices 42, 44 y 46. [6] En 1974, Faulkner y Younger publicaron dos gráficos más: los gráficos de Faulkner-Younger en 42 y 44 vértices. [7]
Finalmente, Holton y McKay demostraron que hay exactamente seis poliedros no hamiltonianos de 38 vértices que tienen cortes de tres bordes no triviales. Se forman reemplazando dos de los vértices de un prisma pentagonal por el mismo fragmento utilizado en el ejemplo de Tutte. [8]
Referencias
- ^ Weisstein, Eric W. "Gráfico de Tutte" . MathWorld .
- ^ Tait, PG (1884), "Listing's Topologie ", Philosophical Magazine , quinta serie, 17 : 30–46. Reimpreso en Scientific Papers , vol. II, págs. 85–98.
- ^ Tutte, WT (1946), "On Hamiltonian circuits" (PDF) , Journal of the London Mathematical Society , 21 (2): 98-101, doi : 10.1112 / jlms / s1-21.2.98.
- ^ Lederberg, J. "DENDRAL-64: un sistema para la construcción, enumeración y notación de moléculas orgánicas como estructuras de árboles y gráficos cíclicos. Parte II. Topología de gráficos cíclicos". Informe provisional para la Administración Nacional de Aeronáutica y del Espacio. Conceder NsG 81-60. 15 de diciembre de 1965. [1] .
- ^ Weisstein, Eric W. "Gráfico de Barnette-Bosák-Lederberg" . MathWorld .
- ^ Grinberg, EJ "Gráficos planos homogéneos de grado tres sin circuitos hamiltonianos". Matemáticas de Letonia. Anuario, Izdat. Zinatne, Riga 4, 51–58, 1968.
- ^ Faulkner, GB y menores, DH "Mapas planos cúbicos no hamiltonianos". Matemáticas discretas. 7, 67–74, 1974.
- ^ Holton, DA; McKay, BD (1988), "Las gráficas planas cúbicas conectadas 3 no hamiltonianas más pequeñas tienen 38 vértices", Journal of Combinatorial Theory, Serie B , 45 (3): 305–319, doi : 10.1016 / 0095-8956 (88 ) 90075-5.