Граф Хортона

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

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

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

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

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

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

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

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

${\displaystyle (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)}$ ${\displaystyle (x^{10}-23x^{8}+188x^{6}-644x^{4}+803x^{2}-101)^{2}}$ ${\displaystyle (x^{10}-20x^{8}+143x^{6}-437x^{4}+500x^{2}-59)}$.