Граф Хортона

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

Граф Хортона — 3-регулярный граф с 96 вершинами и 144 рёбрами, открытый Джозефом Хортоном. Бонди и Мурти опубликовали в 1976 этот граф в качестве контрпримера гипотезе Татта, что любой кубический 3-связный двудольный граф является гамильтоновым.

Связанные графы

После публикации графа Хортона были найдены некоторые другие меньшие контрпримеры Татта. Среди них — граф с 92 вершинами, опубликованный Хортоном в 1982, граф с 78 вершинами, который опубликовал Оуэнс в 1983, и два графа Эллингема – Хортона (с 54 и 78 вершинами).

Первый граф Эллингема – Хортона был опубликован Эллингемом в 1981 и имел 78 вершин. В то время это был самый маленький известный контрпример гипотезе Татта. Второй граф был опубликован Эллингемом и Хортоном в 1983 и он имеет 54 вершин. Никаких меньших негамильтоновых кубических 3-связных двудольных графов в настоящее время не известно.

Свойства

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

Граф Хортона имеет хроматическое число 2, хроматический индекс 3, радиус 10, диаметр 10 и обхват 6. Он также является рёберно 3-связным графом.

Алгебраические свойства

Группа автоморфизмов графа Хортона имеет порядок 96 и изоморфна Z/2Z×Z/2Z×S₄, прямому произведению четверной группы Клейна и симметрической группы S₄.

Характеристический многочлен графа Хортона равен $(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.
• 
  Хроматический индекс графа Хортона равен 3.
• 
  Граф Эллингема — Хортона, наименьший контрпример гипотезы Татта.