| Граф Хортона | |
|---|---|
 Граф Хортона | |
| Назван в честь | Джозеф Хортон |
| Вершин | 96 |
| Рёбер | 144 |
| Радиус | 10 |
| Диаметр | 10 |
| Обхват | 6 |
| Автоморфизмы |
96 (<b>Z</b>/2<b>Z</b>×Z/2Z×S4) |
| Хроматическое число | 2 |
| Хроматический индекс | 3 |
| Свойства |
кубический двудольный |
 Медиафайлы на Викискладе | |
Граф Хортона — 3-регулярный граф с 96 вершинами и 144 рёбрами, открытый Джозефом Хортоном[1]. Бонди и Мурти опубликовали в 1976 этот граф в качестве контрпримера гипотезе Татта, что любой кубический 3-связный двудольный граф является гамильтоновым[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.
Характеристический многочлен графа Хортона равен .
Галерея
-
Хроматическое число графа Хортона равно 2. -
Хроматический индекс графа Хортона равен 3. -
Граф Эллингема — Хортона, наименьший контрпример гипотезы Татта.
Примечания
- ↑ Weisstein, Eric W. Horton graph (англ.) на сайте Wolfram MathWorld.
- ↑ Tutte, 1971/72, с. 203-208.
- ↑ Bondy, Murty, 1982, с. 240.
- ↑ Horton, 1982, с. 35-41.
- ↑ Owens, 1983, с. 327-330.
- ↑ Ellingham, 1981.
- ↑ Ellingham, Horton, 1983, с. 350-353.
- ↑ 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. Архивировано 18 мая 2024 года.
Эта страница в последний раз была отредактирована 31 января 2024 в 11:31.
Обычно почти сразу, изредка в течении часа.