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

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