Граф Винера — Арайи

Перейти к навигацииПерейти к поиску
граф Винера — Арайи
Вершин 42
Рёбер 67
Радиус 5
Диаметр 7
Обхват 4
Хроматическое число 3
Хроматический индекс 4
Свойствагипогамильтонов
планарный

Граф Винера — Арайи — граф с 42 вершинами и 67 рёбрами. Он гипогамильтонов, что означает, что сам по себе он не имеет гамильтонова цикла, но любой граф, образованный удалением отдельной вершины, гамильтонов. Он также планарен.

История

Гипогамильтоновы графы первым изучал Сусилье в статье Problèmes plaisants et délectables (1963)[1]. В 1967 году Линдгрен построил бесконечную последовательность гипогамильтоновых графов[2]. Он указал на Годена, Герца и Росси[3], а затем на Ба́сакера и Саати[4] как пионеров данной области.

С самого начала наименьший гипогамильтонов граф известен — это Граф Петерсена. Однако охота на наименьший планарный гипогамильтонов граф продолжается. Вопрос первым поставил Вацлав Хватал в 1973 году[5]. Первый ответ дал в 1976 году Карстен Томассен, который представил построение графа со 105 вершинами, 105-граф Томассена[6]. В 1979 году Хатцель улучшил этот результат, найдя планарный гипогамильтонов граф с 57 вершинами — граф Хатцеля[7]. Эта граница была понижена в 2007 году 48-графом Замфиреску[8].

В 2009 году граф, построенный Габором Винером и Макото Арайи, (с 42 вершинами) стал наименьшим известным планарным гипогамильтоновым графом[9][10]. В своей статье Винер и Арайа высказали гипотезу, что их граф является оптимальным аргументом, почему число (42) появилось как ответ на главный вопрос жизни, вселенной и всего такого из Автостопом по галактике, романа Дугласа Адамса.

Примечания

  1. ↑ Sousselier, 1963, с. 405–406.
  2. ↑ Lindgren, 1967, с. 1087–1089.
  3. ↑ Gaudin, Herz, Rossi, 1964, с. 214–218.
  4. ↑ Busacker, Saaty, 1965.
  5. ↑ Chvátal, 1973, с. 33–41.
  6. ↑ Thomassen, 1976, с. 377–389.
  7. ↑ Hatzel, 1979, с. 213–216.
  8. ↑ Zamfirescu, Zamfirescu, 2007, с. 338–342.
  9. ↑ Wiener, Araya, 2009.
  10. ↑ Wiener, Araya, 2011, с. 55–68.

Литература

  • Sousselier R. Problème no. 29: Le cercle des irascibles. — Rev. Franç. Rech. Opérationnelle, 1963. — Т. 7. — С. 405–406.
  • Lindgren W. F. An infinite class of hypohamiltonian graphs // American Mathematical Monthly. — 1967. — Т. 74. — С. 1087–1089. — doi:10.2307/2313617.
  • Gaudin T., Herz P., Rossi. Solution du problème No. 29 (фр.) // Rev. Franç. Rech. Opérationnelle. — 1964. — Vol. 8. — P. 214–218.
  • Busacker R. G., Saaty T. L. Finite Graphs and Networks. — 1965.
    • Басакер Р., Саати Т. Конечные графы и сети. — М.: «Наука», 1974..
  • Chvátal V. Flip-flops in hypo-Hamiltonian graphs // Canadian Mathematical Bulletin. — 1973. — Т. 16. — С. 33–41. — doi:10.4153/cmb-1973-008-9.
  • Carsten Thomassen. Planar and infinite hypohamiltonian and hypotraceable graphs // Discrete Mathematics. — 1976. — Т. 14, вып. 4. — С. 377–389. — doi:10.1016/0012-365x(76)90071-6.
  • Wolfgang Hatzel. Ein planarer hypohamiltonscher Graph mit 57 Knoten (Ge) // Mathematische Annalen. — 1979. — Т. 243, вып. 3. — С. 213–216. — doi:10.1007/BF01424541.
  • Carol T. Zamfirescu, Tudor I. Zamfirescu. A planar hypohamiltonian graph with 48 vertices // Journal of Graph Theory. — 2007. — Т. 55, вып. 4. — С. 338–342. — doi:10.1002/jgt.20241.
  • Gábor Wiener, Makoto Araya. The ultimate question. — 2009. — Апрель. — Bibcode: 2009arXiv0904.3012W. — arXiv:0904.3012.
  • Gábor Wiener, Makoto Araya. On planar hypohamiltonian graphs // Journal of Graph Theory. — 2011. — Т. 67, вып. 1. — С. 55–68. — doi:10.1002/jgt.20513.

Ссылки

Weisstein, Eric W. Wiener-Araya Graph (англ.) на сайте Wolfram MathWorld.