Граф Хортона

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

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

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

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

Свойства

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

Граф Хортона имеет хроматическое число 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} - 23 x^{8} + 188 x^{6} - 644 x^{4} + 803 x^{2} - 101)^{2}$ $(x^{10} - 20 x^{8} + 143 x^{6} - 437 x^{4} + 500 x^{2} - 59)$ .