Граф Хортона

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

Граф Хортона

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

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

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

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

Свойства

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

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

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

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

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

Галерея

Примечания

  1. Weisstein, Eric W. Horton graph (англ.) на сайте Wolfram MathWorld.
  2. Tutte, 1971/72, с. 203-208.
  3. Bondy, Murty, 1982, с. 240.
  4. Horton, 1982, с. 35-41.
  5. Owens, 1983, с. 327-330.
  6. Ellingham, 1981.
  7. Ellingham, Horton, 1983, с. 350-353.
  8. Ejov, Pugacheva, Rossomakhine, Zograf, 2006.

Литература

  • W. T. Tutte. On the 2-Factors of Bicubic Graphs // Disc. Math. — 1971/72. Вып. 1.
  • J. A. Bondy, U. S. R. Murty. Graph Theory with Applications. — Fifth Printing. — New York: North Holland, 1982. — ISBN 0-444-19451-7.
  • J. D. Horton. On Two-Factors of Bipartite Regular Graphs // Disc. Math. — 1982. Вып. 41.
  • P. J. Owens. Bipartite Cubic Graphs and a Shortness Exponent // Disc. Math. — 1983. Вып. 44.
  • M. N. Ellingham. Non-Hamiltonian 3-Connected Cubic Partite Graphs, Research Report No. 28. — Melbourne: Univ. Melbourne, 1981. — (Dept. of Math.).
  • M. N. Ellingham, J. D. Horton. Non-Hamiltonian 3-Connected Cubic Bipartite Graphs // J. Combin. Th. Ser. B. — 1983. Вып. 34.
  • V. Ejov, N. Pugacheva, S. Rossomakhine, P. Zograf. An effective algorithm for the enumeration of edge colorings and Hamiltonian cycles in cubic graphs. — 2006. arXiv:math/0610779v1. Архивировано 28 февраля 2022 года.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.