En la matemática campo de la teoría de grafos , los gráficos de Ellingham-Horton son dos 3- grafo regular en 54 y 78 vértices: la Ellingham-Horton 54-gráfico y la Ellingham-Horton 78-gráfico . [1] Llevan el nombre de Joseph D. Horton y Mark N. Ellingham , sus descubridores. Estos dos gráficos proporcionan contraejemplos a la conjetura de WT Tutte de que todo gráfico bipartito cúbico de 3 conexiones es hamiltoniano . [2] El grosor del libro del gráfico de 54 de Ellingham-Hortony el gráfico 78 de Ellingham-Horton es 3 y los números de cola 2. [3]
Gráficos de Ellingham-Horton | |
---|---|
Lleva el nombre de | Joseph Horton y Mark Ellingham |
Vértices | 54 (54 gráficos) 78 (78 gráficos) |
Bordes | 81 (54 gráficos) 117 (78 gráficos) |
Radio | 9 (54 gráficos) 7 (78 gráficos) |
Diámetro | 10 (54 gráficos) 13 (78 gráficos) |
Circunferencia | 6 (ambos) |
Automorfismos | 32 (54 gráficos) 16 (78 gráficos) |
Número cromático | 2 (ambos) |
Índice cromático | 3 (ambos) |
Espesor del libro | 3 (ambos) |
Número de cola | 2 (ambos) |
Propiedades | Cúbico (ambos) Bipartito (ambos) Regular (ambos) |
Tabla de gráficos y parámetros |
El primer contraejemplo de la conjetura de Tutte fue el gráfico de Horton , publicado por Bondy y Murty (1976) . [4] Después del gráfico de Horton, se encontraron varios contraejemplos más pequeños a la conjetura de Tutte. Entre ellos se encuentran un gráfico de 92 vértices de Horton (1982) , [5] un gráfico de 78 vértices de Owens (1983) , [6] y los dos gráficos de Ellingham-Horton.
El primer gráfico de Ellingham-Horton fue publicado por Ellingham (1981) y es de orden 78. [7] En ese momento era el contraejemplo más pequeño conocido de la conjetura de Tutte. El segundo gráfico de Ellingham-Horton fue publicado por Ellingham & Horton (1983) y es de orden 54. [8] En 1989, se descubrió el gráfico de Georges, el gráfico bipartito cúbico no hamiltoniano de 3 conexiones más pequeño que se conoce actualmente, que contiene 50 vértices. [9]
Galería
El número cromático del gráfico de 54 de Ellingham-Horton es 2.
El índice cromático del gráfico de 54 de Ellingham-Horton es 3.
El número cromático del gráfico 78 de Ellingham-Horton es 2.
El índice cromático del gráfico 78 de Ellingham-Horton es 3.
Referencias
- ^ Weisstein, Eric W. "Conjetura de Tutte" . MathWorld .
- ^ Tutte, WT (1971), "Sobre los 2 factores de las gráficas bicúbicas", Matemáticas discretas , 1 (2): 203-208, doi : 10.1016 / 0012-365X (71) 90027-6.
- ^ Jessica Wolz, Diseños lineales de ingeniería con SAT. Tesis de maestría, Universität Tübingen, 2018
- ^ Bondy, JA ; Murty, USR (1976), Teoría de grafos con aplicaciones , Nueva York: Holanda Septentrional, p. 240 , ISBN 0-444-19451-7
- ^ Horton, JD (1982), "Sobre dos factores de gráficas regulares bipartitas", Matemáticas discretas , 41 (1): 35–41, doi : 10.1016 / 0012-365X (82) 90079-6.
- ^ Owens, PJ (1983), "Gráficas cúbicas bipartitas y un exponente de brevedad", Matemáticas discretas , 44 (3): 327–330, doi : 10.1016 / 0012-365X (83) 90201-7.
- ^ Ellingham, MN (1981), Gráficos de partitos cúbicos conectados de 3 no hamiltonianos , Informe de investigación 28, Melbourne: Departamento de Matemáticas, Univ. Melbourne.
- ^ Ellingham, MN; Horton, JD (1983), "Gráficos bipartitos cúbicos conectados de 3 no hamiltonianos", Journal of Combinatorial Theory, Serie B , 34 (3): 350–353, doi : 10.1016 / 0095-8956 (83) 90046-1.
- ^ Georges, JP (1989), "Gráficos bicúbicos no hamiltonianos", Journal of Combinatorial Theory, Serie B , 46 (1): 121-124, doi : 10.1016 / 0095-8956 (89) 90012-9.