Ця стаття є сирим перекладом з іншої мови Можливо вона створена за допомогою машинного перекладу або перекладачем який н

У математичної області теорії графів, граф Хортона або 96-граф Хортона являє собою 3-регулярний граф з 96 вершинами і 144 реберами, виявлених Джохефом Хортоном. Опубліковано Бонді і Мурті в 1976 році, вона забезпечує контрприклад до гіпотези Татта, що кожен кубічний 3-зв'язний двочастковий граф є гамільтоновим графом.

Граф Хортон

Названо на честь	Джозефа Хортона
(Вершин)	96
(Ребер)	144
(Радіус)	10
(Діаметр)	10
(Обхват)	6
(Автоморфізм)	96 (×Z/2Z×)
Хроматичне число	2
Хроматичний індекс	3
Число черг	2
Властивості	кубічний двочастковий

Після графу Хортона, були знайдені кілька невеликих контрприкладів до гіпотези Татта. Серед них 92 вершин графу по Хортону, опубліковані в 1982 році, 78 вершин графу по Овенсу опублікований в 1983 році й два графу Єгингхема-Хортона (54 і 78 вершин).

Перший граф Єгингхема — Хортона був опублікований в 1981 році і був близько 78. В той час це була найменший контрприклад до гіпотези Татта. Другий був опублікований Єгингхемем і Хортоном в 1983 році і був близько 54. Чи є менше негамільтонів кубічний 3-зв'язний двочастковий граф на даний час невідомо.

У негамільтонова кубічного графу з великою кількістю довгих циклів, граф Хортона забезпечує хороший орієнтир для програм, які виконують пошук гамільтонових циклів.

Графік Хортон має хроматичний номер 2, хроматичний індекс 3, радіус 10, діаметр 10 і обхват 6. Це також реберно 3-зв'язний граф.

Група автоморфізмів графу Хортона має порядок 96 і ізоморфна з/2з×з/2з×з₄, прямий добуток чверті групи Клейна і симетрична група S4.

Характеристичний многочлен графу Хортон:

$(x-3)(x-1)^{14}x^{4}(x+1)^{14}(x+3)(x^{2}-5)^{3}(x^{2}-3)^{11}(x^{2}-x-3)(x^{2}+x-3)$ $(x^{10}-23x^{8}+188x^{6}-644x^{4}+803x^{2}-101)^{2}$ $(x^{10}-20x^{8}+143x^{6}-437x^{4}+500x^{2}-59)$ .

Галерея

У хроматичному числі з Хортон графік 2.
Хроматичне число графу Хортона 2.
Элингхем-Хортон 54-граф, менший контрприклад до гіпотези Татта.

Посилання

Tutte, W. T. «On the 2-Factors of Bicubic Graphs.»
Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications.
Horton, J. D. «On Two-Factors of Bipartite Regular Graphs.»
Owens, P. J. «Bipartite Cubic Graphs and a Shortness Exponent.»
V. Ejov, N. Pugacheva, S. Rossomakhine, P. Zograf «An effective algorithm for the enumeration of edge colorings and Hamiltonian cycles in cubic graphs» arXiv:math/0610779v1.

[1] Tutte, W. T. «On the 2-Factors of Bicubic Graphs.»

[2] Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications.

[3] Horton, J. D. «On Two-Factors of Bipartite Regular Graphs.»

[4] Owens, P. J. «Bipartite Cubic Graphs and a Shortness Exponent.»

[5] V. Ejov, N. Pugacheva, S. Rossomakhine, P. Zograf «An effective algorithm for the enumeration of edge colorings and Hamiltonian cycles in cubic graphs» arXiv:math/0610779v1.