Граф Хортона — 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×S4, прямому произведению четверной группы Клейна и симметрической группы S4.
Характеристический многочлен графа Хортона равен .
Галерея
Примечания
Литература
Категория:Графы, имеющие собственные названия Категория:Регулярные графы