Это не официальный сайт wikipedia.org 01.01.2023

Граф Эллингема — Хортона — Википедия
Википедия

Граф Эллингема — Хортона

Статья Обсуждение

Графы Эллингема — Хортона — два 3-регулярных графа с 54 и 78 вершинами — 54-граф Эллингема — Хортона и 78-граф Эллингема — Хортона[1]. Графы названы именами Джозефа Хортона и Марка Эллингема, которые их открыли. Эти два графа дают контрпримеры гипотезе Уильяма Татта о том, что каждый кубический 3-связный двудольный граф является гамильтоновым[2].

Графы Эллингема — Хортона
54-граф Эллингема — Хортона.
54-граф Эллингема — Хортона.
Назван в честь Джозеф Хортон и Марк Эллингем
Вершин 54 (54-граф)
78 (78-граф)
Рёбер 81 (54-граф)
117 (78-граф)
Радиус 9 (54-граф)
7 (78-граф)
Диаметр 10 (54-граф)
13 (78-граф)
Обхват 6 (оба)
Автоморфизмы 32 (54-граф)
16 (78-граф)
Хроматическое число 2 (оба)
Хроматический индекс 3 (оба)
Свойства кубические (оба)
двудольные (оба)
регулярные (оба)

Первым контрпримером гипотезы Татта был граф Хортона, который опубликовали Бодни и Мёрти[3]. После графа Хортона было найдено несколько меньших контрпримеров гипотезе Татта. Среди них находятся 92-вершинный граф Хортона[4], 78-вершинный граф Овенса[5] и два графа Эллингема — Хортона.

Первый граф Эллингема — Хортона опубликовал Эллингем и он имеет порядок 78[6]. В то время граф был наименьшим известным контрпримером гипотезе Татта. Второй граф Эллингема — Хортона опубликовали Эллингем и Хортон и он имеет порядок 54[7]. В 1989 был открыт на настоящее время наименьший негамильтонов 3-связный кубический двудольный граф Жоржа, содержащий 50 вершин[8].

ГалереяПравить

ПримечанияПравить

  1. ↑ Weisstein, Eric W. Tutte Conjecture (англ.) на сайте Wolfram MathWorld.
  2. ↑ Tutte, 1971, с. 203–208.
  3. ↑ Bondy, Murty, 1976, с. 240.
  4. ↑ Horton, 1982, с. 35–41.
  5. ↑ Owens, 1983, с. 327–330.
  6. ↑ Ellingham, 1981.
  7. ↑ Ellingham, Horton, 1983, с. 350–353.
  8. ↑ Georges, 1989, с. 121–124.

ЛитератураПравить

  • Tutte W. T. On the 2-factors of bicubic graphs // Discrete Mathematics. — 1971. — Т. 1, вып. 2. — С. 203—208. — doi:10.1016/0012-365X(71)90027-6.
  • Bondy J. A., Murty U. S. R. Graph Theory with Applications. — New York: North Holland, 1976. — С. 240. — ISBN 0-444-19451-7. Архивная копия от 13 апреля 2010 на Wayback Machine
  • Horton J. D. On two-factors of bipartite regular graphs // Discrete Mathematics. — 1982. — Т. 41, вып. 1. — С. 35—41. — doi:10.1016/0012-365X(82)90079-6.
  • Owens P. J. Bipartite cubic graphs and a shortness exponent // Discrete Mathematics. — 1983. — Т. 44, вып. 3. — С. 327—330. — doi:10.1016/0012-365X(83)90201-7.
  • Ellingham M. N. Non-Hamiltonian 3-connected cubic partite graphs. — Melbourne: Dept. of Math., Univ. Melbourne, 1981. — (Research Report 28).
  • Ellingham M. N., Horton J. D. Non-Hamiltonian 3-connected cubic bipartite graphs // Journal of Combinatorial Theory, Series B. — 1983. — Т. 34, вып. 3. — С. 350—353. — doi:10.1016/0095-8956(83)90046-1.
  • Georges J. P. Non-hamiltonian bicubic graphs // Journal of Combinatorial Theory, Series B. — 1989. — Т. 46, вып. 1. — С. 121—124. — doi:10.1016/0095-8956(89)90012-9.
Источник — https://ru.wikipedia.org/w/index.php?title=Граф_Эллингема_—_Хортона&oldid=112533756