ГлавнаяАрхивСравнение достаточных условий гамильтоновости графа, основанных на степенях вершин

Сравнение достаточных условий гамильтоновости графа, основанных на степенях вершин | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/6

Для всех графов с числом вершин до 12 сравниваются наиболее популярные достаточные условия гамильтоновости, основанные на степенях вершин графа: теоремы Дирака, Оре, Поша, Хватала и Бонди - Хватала. Для каждого условия подсчитано число графов, ему удовлетворяющих. Наилучшие результаты показывает достаточное условие гамильтоновости, предложенное Бонди и Хваталом в 1976 г., - этому условию удовлетворяют около 90 % гамильтоновых графов.
  • Title Сравнение достаточных условий гамильтоновости графа, основанных на степенях вершин
  • Headline Сравнение достаточных условий гамильтоновости графа, основанных на степенях вершин
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 45
  • Date:
  • DOI 10.17223/20710410/45/6
Ключевые слова
гамильтонов граф, FHCP, Hamiltonian graph, Dirac's theorem, Ore's theorem, Posa's theorem, Chvatal's theorem, theorem by Bondy and Chvatal, теорема Дирака, теорема Оре, теорема Поша, теорема Хватала, теорема Бонди-Хватала
Авторы
Ссылки
Dirac G. A. Some theorems on abstract graphs // Proc. London Math. Soc. 1952. V. 2. P. 69-81
Ore O. Note on Hamilton circuits // Amer. Math. Monthly. 1960. V. 67. P. 55
Ore O. Arc coverings of graphs // Ann. Mat. Pura Appl. 1961. V. 55. P. 315-322
Posa L. On the circuits of finite graphs // Magyar Tud. Akad. Mat. Kutatd Int. Kozl. 1963. V. 8. P. 355-361
Chvatal V. On Hamilton's ideals // J. Combin. Theory. 1972. V. 12. P. 163-168
Bondy J. A. and Chvatal V. A method in graph theory // Discr. Math. 1976. V. 15. Iss. 2. P. 111-135
Gould R. J. Updating the Hamiltonian problem - A survey // J. Graph Theory. 1991. V. 15. No. 2. P. 121-157
Gould R. J. Advances on the Hamiltonian problem - A survey // Graphs and Combinatorics. 2003. V. 19. P. 7-52
DeLeon M. A study of sufficient conditions for Hamiltonian cycles // Rose - Hulman Undergraduate Mathematics J. 2000. V. 1. Iss. 1. Article 6. P. 129-145
Li H. Generalizations of Diracs theorem in Hamiltonian graph theory - A survey // Discr. Math. 2013. V. 313. P. 2034-2053
Харари Ф. Теория графов. М.: Мир, 1973. 300 с
Diestel R. Graph Theory. Heidelberg: Springer Verlag, 2017. 447 p
Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384 с
Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика. Графы, матроиды, алгоритмы. Ижевск: НИЦ «РХД», 2001. 288 с
Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003. 1104 с
Омельченко А. В. Теория графов. М.: МЦНМО, 2018. 416 с
Абросимов М. Б. О достаточном условии Гудмана - Хедетниеми гамильтоновости графа // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2018. Т. 18. Вып. 3. С. 347-353
McKay B. D. and Piperno A. Practical graph isomorphism. II // J. Symbolic Computation. 2014. No. 60. P. 94-112
The On-Line Encyclopedia of Integer Sequences, 2018 http://oeis.org
Haythorpe M. FHCP Challenge Set: The first set of structurally difficult instances of the Hamiltonian cycle problem // Bulletin of the ICA. 2018. V. 83. P. 98-107
Reinelt G. http://www.iwr.uni-heidelberg.de/groups/comopt∕software∕TSPLIB95∕- TSPLIB, 2018
Сравнение достаточных условий гамильтоновости графа, основанных на степенях вершин | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/6
Сравнение достаточных условий гамильтоновости графа, основанных на степенях вершин | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/6