En el campo matemático de la teoría de grafos , el gráfico de Tietze es un grafo cúbico no dirigido con 12 vértices y 18 aristas. Lleva el nombre de Heinrich Franz Friedrich Tietze , quien demostró en 1910 que la franja de Möbius se puede subdividir en seis regiones que se tocan entre sí, tres a lo largo del límite de la franja y tres a lo largo de su línea central, y por lo tanto, los gráficos que están incrustados en la tira de Möbius puede requerir seis colores . [1] Los segmentos de límite de las regiones de la subdivisión de Tietze (incluidos los segmentos a lo largo del límite de la propia tira de Möbius) forman una incrustación del gráfico de Tietze.
Gráfico de Tietze | |
---|---|
Vértices | 12 |
Bordes | 18 |
Radio | 3 |
Diámetro | 3 |
Circunferencia | 3 |
Automorfismos | 12 ( D 6 ) |
Número cromático | 3 |
Índice cromático | 4 |
Propiedades | Snark cúbico |
Tabla de gráficos y parámetros |
Relación con el gráfico de Petersen
La gráfica de Tietze se puede formar a partir de la gráfica de Petersen reemplazando uno de sus vértices con un triángulo . [2] [3] Al igual que el gráfico de Tietze, el gráfico de Petersen forma el límite de seis regiones que se tocan mutuamente, pero en el plano proyectivo en lugar de en la tira de Möbius. Si se corta un agujero de esta subdivisión del plano proyectivo, rodeando un solo vértice, el vértice rodeado se reemplaza por un triángulo de límites de región alrededor del agujero, dando la construcción descrita anteriormente del gráfico de Tietze.
Hamiltonicidad
Tanto el gráfico de Tietze como el gráfico de Petersen son al máximo no hamiltonianos : no tienen un ciclo hamiltoniano , pero dos vértices no adyacentes pueden conectarse mediante una ruta hamiltoniana. [2] La gráfica de Tietze y la gráfica de Petersen son las únicas gráficas no hamiltonianas cúbicas conectadas a 2 vértices con 12 o menos vértices. [4]
A diferencia del gráfico de Petersen, el gráfico de Tietze no es hipohamiltoniano : eliminar uno de sus tres vértices triangulares forma un gráfico más pequeño que sigue siendo no hamiltoniano.
Color de los bordes y combinaciones perfectas
Coloración de bordes El gráfico de Tietze requiere cuatro colores; es decir, su índice cromático es 4. De manera equivalente, los bordes del gráfico de Tietze se pueden dividir en cuatro coincidencias , pero no menos.
El gráfico de Tietze coincide con parte de la definición de snark : es un gráfico cúbico sin puentes que no se puede colorear en 3 bordes. Sin embargo, algunos autores restringen los snarks a gráficos sin 3 ciclos y 4 ciclos, y bajo esta definición más restrictiva, el gráfico de Tietze no es un snark. El gráfico de Tietze es isomorfo al gráfico J 3 , parte de una familia infinita de flores snarks introducidas por R. Isaacs en 1975. [5]
A diferencia del gráfico de Petersen, el gráfico de Tietze puede cubrirse con cuatro coincidencias perfectas . Esta propiedad juega un papel clave en una prueba de que probar si un gráfico puede ser cubierto por cuatro coincidencias perfectas es NP-completo . [6]
Propiedades adicionales
La gráfica de Tietze tiene número cromático 3, índice cromático 4, circunferencia 3 y diámetro 3. El número de independencia es 5. Su grupo de automorfismos tiene orden 12, y es isomorfo al grupo diedro D 6 , el grupo de simetrías de un hexágono , incluyendo ambos rotaciones y reflexiones. Este grupo tiene dos órbitas de tamaño 3 y una de tamaño 6 en los vértices, por lo que este gráfico no es transitivo a los vértices .
Galería
El número cromático del gráfico de Tietze es 3.
El índice cromático del gráfico de Tietze es 4.
El gráfico de Tietze tiene el número de cruce 2 y es 1 plano .
Ver también
- Gráfico de Durero y gráfico de Franklin , otros dos gráficos cúbicos de 12 vértices
Notas
- ^ Tietze, Heinrich (1910), "Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen" [Algunas observaciones sobre el problema de colorear mapas en superficies unilaterales], Informe anual del DMV , 19 : 155-159[ enlace muerto permanente ] .
- ^ a b Clark, L .; Entringer, R. (1983), "Gráficos no hamitianos máximos más pequeños", Periodica Mathematica Hungarica , 14 (1): 57–68, doi : 10.1007 / BF02023582
- ^ Weisstein, Eric W. "Gráfico de Tietze" . MathWorld .
- ^ Punnim, Narong; Saenpholphat, Varaporn; Thaithae, Sermsri (2007), "Gráficos cúbicos casi hamiltonianos" (PDF) , Revista Internacional de Ciencias de la Computación y Seguridad de Redes , 7 (1): 83–86
- ^ Isaacs, R. (1975), "Familias infinitas de grafos trivalentes no triviales que no son coloreables Tait", Amer. Matemáticas. Mensualmente , Asociación de Matemáticas de América, 82 (3): 221–239, doi : 10.2307 / 2319844 , JSTOR 2319844.
- ^ Esperet, L .; Mazzuoccolo, G. (2014), "Sobre gráficos cúbicos sin puentes cuyo conjunto de bordes no puede ser cubierto por cuatro coincidencias perfectas", Journal of Graph Theory , 77 (2): 144-157, arXiv : 1301.6926 , doi : 10.1002 / jgt. 21778 , MR 3246172.