RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика, 2018, том 18, выпуск 3, страницы 347–353 (Mi isu769)  

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

Научный отдел
Информатика

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

М. Б. Абросимов

Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского, Россия, 410012, Саратов, Астраханская, 83

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

Ключевые слова: гамильтоновы графы, запрещенные подграфы.

DOI: https://doi.org/10.18500/1816-9791-2018-18-3-347-353

Полный текст: PDF файл (211 kB)
Список литературы: PDF файл   HTML файл

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

Тип публикации: Статья
УДК: 519.17

Образец цитирования: М. Б. Абросимов, “О достаточном условии Гудмана–Хедетниеми гамильтоновости графа”, Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика, 18:3 (2018), 347–353

Цитирование в формате AMSBIB
\RBibitem{Abr18}
\by М.~Б.~Абросимов
\paper О достаточном условии Гудмана--Хедетниеми гамильтоновости графа
\jour Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика
\yr 2018
\vol 18
\issue 3
\pages 347--353
\mathnet{http://mi.mathnet.ru/isu769}
\crossref{https://doi.org/10.18500/1816-9791-2018-18-3-347-353}
\elib{http://elibrary.ru/item.asp?id=35729006}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/isu769
  • http://mi.mathnet.ru/rus/isu/v18/i3/p347

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. М. Б. Абросимов, “Сравнение достаточных условий гамильтоновости графа, основанных на степенях вершин”, ПДМ, 2019, № 45, 55–63  mathnet  crossref
  • Известия Саратовского университета. Новая серия. Серия Математика. Механика. Информатика
    Просмотров:
    Эта страница:122
    Полный текст:42
    Литература:10
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020