Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Для цитирования:

Абросимов М. Б. О достаточном условии Гудмана–Хедетниеми гамильтоновости графа // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2018. Т. 18, вып. 3. С. 347-353. DOI: 10.18500/1816-9791-2018-18-3-347-353

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
28.08.2018
Полный текст:
(downloads: 36)
Язык публикации: 
русский
Рубрика: 
Тип статьи: 
Научная статья
УДК: 
519.17

О достаточном условии Гудмана–Хедетниеми гамильтоновости графа

Авторы: 
Абросимов Михаил Борисович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Аннотация: 

В 1859 году ирландский математик сэр Уильям Роуэн Гамильтон предложил игру, в которой требовалось найти обход додекаэдра по его ребрам с возвратом в исходную точку. В его честь позднее был назван соответствующий обход графа. Гамильтоновым циклом называется остовной цикл в графе, то есть цикл, проходящий по всем вершинам графа. Граф, содержащий гамильтонов цикл, называется гамильтоновым. В 1952 году Дирак предложил достаточное условие гамильтоновости графа: если степень каждой вершины не меньше половины от общего числа вершин графа, то такой граф является гамильтоновым. Впоследствии было получено много различных достаточных условий гамильтоновости, из которых большую группу образовывают так называемые условия типа Дирака, или достаточные условия, сформулированные в терминах степеней вершин графа: достаточные условия Оре, Поша, Хваталаи другие. В 1976 году Бонди и Хватал предложили конструкцию замыкания графаиновое достаточное условие: если замыкание графа является полным графом, то сам граф является гамильтоновым. Это условие остается одним из наиболее эффективных достаточных условий. В работе исследуется достаточное условие гамильтоновости графов Гудмана–Хедетниеми, которое было предложено в 1974 году. Это условие формулируется в терминах запрещенных подграфов. Дается описание всех графов, удовлетворяющих условию Гудмана–Хедетниеми, и доказывается, что при n > 4 существует только ⌊n/2⌋ + 2 таких n-вершинных графов.

Список источников: 
  1. Харари Ф. Теория графов. М : Мир, 1973. 300 с.
  2. Dirac G. A. Some Theorems on Abstract Graphs // Proc. London Math. Soc. 1952. Vol. s3– 2, iss. 1. P. 69–81. DOI: https://doi.org/10.1112/plms/s3-2.1.69
  3. Ore O. Note on Hamilton Circuits // Amer. Math. Monthly. 1960. Vol. 67, № 1. P. 55. DOI: https://doi.org/10.2307/2308928
  4. Ore O. Arc coverings of graphs // Ann. Mat. Pura Appl. 1961. Vol. 55, iss. 1. P. 315–322. DOI: https://doi.org/10.1007/BF02412090
  5. Posa L. On the circuits of finite graphs // Magyar Tud. Akad. Mat. Kutat´o Int. K¨ozl. 1963. Vol. 8. P. 355–361.
  6. Chvatal V. On Hamilton’s ideals // J. Combinat. Theory (B). 1972. Vol. 12, iss. 2. P. 163– 168. DOI: https://doi.org/10.1016/0095-8956(72)90020-2
  7. Bondy J. A., Chvatal V. A method in graph theory // Discrete Math. 1976. Vol. 15, iss. 2. P. 111–135. DOI: https://doi.org/10.1016/0012-365X(76)90078-9
  8. Fan G. H. New sufficient conditions for cycles in graphs // J. Combinat. Theory (B). 1984. Vol. 37, iss. 3. P. 221–227. DOI: https://doi.org/10.1016/0095-8956(84)90054-6
  9. Faudree R. J., Gould R. J., Jacobson M. S., Schelp R. H. Neighborhood unions and Hamiltonian properties in graphs // J. Combinat. Theory (B). 1989. Vol. 47, iss. 1. P. 1–9. DOI: https://doi.org/10.1016/0095-8956(89)90060-9
  10. Gould R. J. Advances on the Hamiltonian Problem – A Survey // J. Graph Theory. 1991. Vol. 15, iss. 2. P. 121–157. DOI: https://doi.org/10.1002/jgt.3190150204
  11. Li H. Generalizations of Diracs theorem in Hamiltonian graph theory – A survey // Discrete Math. 2013. Vol. 313, iss. 19. P. 2034–2053. DOI: https://doi.org/10.1016/j.disc.2012.11.025
  12. Goodman S. E., Hedetniemi S. T. Sufficient Conditions for a graph to be Hamiltonian // J. Combin Theory (B). 1974. Vol. 16, iss. 2. P. 175–180. DOI: https://doi.org/10.1016/00958956(74)90061-6
Краткое содержание:
(downloads: 37)