Conde Thatta

Conde Thatta

Lleva el nombre de	Guillermo Thomas Tutt
picos	46
costillas	69
Radio	5
Diámetro	ocho
Circunferencia	cuatro
automorfismos	3 ( ) $\mathbb {Z} /3\mathbb {Z}$
Número cromático	3
índice cromático	3
Propiedades	plano cúbico poliédrico
Archivos multimedia en Wikimedia Commons

El gráfico de Tutta es un ejemplo de un gráfico poliédrico cúbico no hamiltoniano . Por lo tanto, sirve como un contraejemplo a la conjetura de Tate , que supuso que cualquier politopo de 3 regulares tiene un ciclo hamiltoniano [1] [2] .

Construido por William Tutt en 1946 [3] . Posteriormente se encontraron otros contraejemplos, en la mayoría de los casos basados en el teorema de Greenberg .

Edificio

El gráfico de Tatta consta de tres piezas idénticas, los llamados fragmentos de Tatta. Un fragmento tiene la propiedad de que de las tres aristas que salen de él, una está necesariamente presente en el ciclo hamiltoniano en cualquier grafo con tal fragmento. Los bordes "requeridos" del fragmento se acercan al vértice central. Dado que cualquier ciclo hamiltoniano solo puede usar dos de ellos, no existe un ciclo hamiltoniano.

El grafo resultante es 3-conexo y plano , por lo que según el teorema de Steinitz, este grafo es un grafo politópico. El gráfico tiene 25 caras.

Geométricamente, se puede obtener de un tetraedro (cada cara del cual corresponde a cuatro caras grandes con 9 aristas, tres de las cuales están entre pares de fragmentos, y la cuarta forma la cara exterior) cortando repetidamente tres de sus vértices.

Propiedades

Tiene 46 vértices y 69 aristas.
El número cromático de la gráfica es 3,
El índice cromático es 3,
la circunferencia es 4
El diámetro es 8.
El gráfico es 3-conexo y plano . Por lo tanto, por el teorema de Steinitz , este gráfico es un gráfico de un poliedro. (El número de caras es 25.)
El grupo de automorfismos del grafo de Tutt es , un grupo cíclico de tercer orden. $\mathbb {Z} /3\mathbb {Z}$
Polinomio característico del gráfico: ${\ estilo de visualización (x-3)(x^{15}-22x^{13}+x^{12}+184x^{11}-26x^{10}-731x^{9}+199x^{8} +1383x^{7}-576x^{6}-1061x^{5}+561x^{4}+233x^{3}-151x^{2}+4x+4)^{2}}$ ${\ estilo de visualización (x^{15}+3x^{14}-16x^{13}-50x^{12}+94x^{11}+310x^{10}-257x^{9}-893x^{8 }+366x^{7}+1218x^{6}-347x^{5}-717x^{4}+236x^{3}+128x^{2}-56x+4)}$ .

Variaciones

Aunque el gráfico de Tutta es históricamente el primer gráfico poliédrico no hamiltoniano regular de 3, no es el más pequeño de ellos.

En 1965, Lederberg encontró un gráfico con 38 vértices ( el gráfico de Barnett-Bosack-Lederberg ) [4] [5] ,
En 1968, Greenberg construyó varios contraejemplos más para la conjetura de Tate: gráficos de Greenberg con 42, 44 y 46 vértices [6] , y en 1974 se encontraron dos gráficos más (gráficos de Faulkner-Yanger) con 42 y 44 vértices [7] . En 1988, se descubrió que hay exactamente seis gráficos poliédricos no hamiltonianos con 38 vértices que tienen secciones no triviales de tres aristas, se forman reemplazando dos vértices de un prisma pentagonal con el mismo fragmento que se usa en el ejemplo de Tutt [8 ] .

Notas

↑ PG Tait. Topología del Listado // Revista Filosófica (5ª ser.). - 1884. - T. 17 . — P. 30–46 . . Artículo reimpreso en Scientific Papers , vol. II, págs. 85-98.
↑ 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 .
↑ Weisstein, Eric W. Tutte 's Graph en el sitio web de Wolfram MathWorld .
↑ Lederberg, J. "DENDRAL-64: Un sistema para la construcción, enumeración y notación informática de moléculas orgánicas como estructuras de árbol y gráficos cíclicos". Parte II. Topología de grafos cíclicos. Informe Interino a la Administración Nacional de Aeronáutica y del Espacio. Concesión NsG 81-60. 15 de diciembre de 1965. [1] Archivado el 20 de mayo de 2014 en Wayback Machine .
↑ Weisstein, Eric W. Barnette-Bosák-Lederberg Gráfico en el sitio web Wolfram MathWorld .
↑ E. Ya. Grinberg. Gráficos planos homogéneos de grado tres sin ciclos hamiltonianos. // Latv. Matemáticas. anuario. - T. 4 . — págs. 51-58. .
↑ G. B. Faulkner, D. H. Younger. Mapas planos cúbicos no hamiltonianos. // Matemáticas Discretas . - 1974. - T. 7 . - S. 67-74 .
↑ DA Holton, BD McKay. Los gráficos planos cúbicos conectados en 3 no hamiltonianos más pequeños tienen 38 vértices // Journal of Combinatorial Theory, Series B. - 1988. - V. 45 , no. 3 . — S. 305–319 . - doi : 10.1016/0095-8956(88)90075-5 .