ДОСТАТОЧНОЕ УСЛОВИЕ ГАМИЛЬТОНОВОСТИ ГРАФА, ИСПОЛЬЗУЮШЕЕ ПОНЯТИЕ РАССТОЯНИЯ

摘要

Аннотация. В 1990 г. Г.Т. Чен доказал, что двусвязный граф G порядка n, каждая пара несмежных вершин которого х, у удовлетворяет неравенству 2|N(х) U N(у)| + d(x) + d(у) ≥ 2n — 1, является гамильтоновым. В данной статье мы показываем, что для гамильтоновости двусвязного графа G порядка n достаточно, чтобы неравенство 2|N(х) U N(y)|+ d(х) + d(у) ≥ 2n — 1 выполнялось для каждой пары несмежных вершин х, у таких, что d(х, у) = 2.