RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия высших учебных заведений. Математика // Архив

Изв. вузов. Матем., 2012, номер 4, страницы 46–52 (Mi ivm8593)

Достаточное условие гамильтоновости графа, использующее понятие расстояния

Кевен Цаоa, Лин Юa, Цан Пинb

a Цюнчжоуский университет, математический факультет, Хайнань, Китайская народная республика
b Университет Западного Мичигана, факультет математики и статистики, Мичиган, США

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

Ключевые слова: гамильтонов граф, условие Оре, условие объединения окрестностей, условие Чена, новое достаточное условие.

УДК: 517.175

Поступила: 29.10.2010


 Англоязычная версия: Russian Mathematics (Izvestiya VUZ. Matematika), 2012, 56:4, 38–43

Реферативные базы данных:


© МИАН, 2024