Образец для цитирования:

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


Рубрика: 
УДК: 
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

 

Краткое содержание (на английском языке): 
Полный текст в формате PDF: