RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика. Приложение // Архив

ПДМ. Приложение, 2016, выпуск 9, страницы 103–105 (Mi pdma255)

Прикладная теория автоматов и графов

О количестве оптимальных $1$-гамильтоновых графов с числом вершин до $26$ и $28$

М. Б. Абросимов, С. А. Сухов

Саратовский государственный университет имени Н. Г. Чернышевского, г. Саратов

Аннотация: Граф называется $1$-вершинно(рёберно)-гамильтоновым, если после удаления любой его вершины (ребра) получившийся граф является гамильтоновым; $1$-вершинно(рёберно)-гамильтонов граф называется оптимальным, если он имеет минимально возможное число рёбер среди всех $1$-вершинно(рёберно)-гамильтоновых графов с тем же числом вершин. В работе перепроверены полученные ранее данные для оптимальных $1$-вершинно- и $1$-рёберно-гамильтоновых графов, а также удалось вычислить новые значения для $28$ вершин.

Ключевые слова: оптимальный $1$-гамильтонов граф, минимальное $1$-расширение цикла, отказоустойчивость.

УДК: 519.17

DOI: 10.17223/2226308X/9/40



© МИАН, 2024