График Сусселье - Sousselier graph

График Сусселье
Сусселье graph.svg
Вершины16
Края27
Радиус2
Диаметр3
Обхват5
Автоморфизмы2
Хроматическое число3
Хроматический индекс5
Толщина книги3
Номер очереди2
Таблица графиков и параметров

В График Сусселье в теория графов, а гипогамильтонов граф с 16 вершинами и 27 ребрами. Она имеет толщина книги 3 и номер очереди 2.[1]

История

Гипогамильтоновы графы были впервые изучены Сусселье в Problèmes plaisants et délectables (1963).[2]

В 1967 году Линдгрен построил бесконечную последовательность гипогамильтоновых графов, все графы которой имеют 6k+10 вершин на каждое целое число k.[3]Та же последовательность гипогамильтоновых графов независимо построена Сусселье.[4] В 1973 г. Chvátal объясняет в научной статье, как ребра могут быть добавлены к некоторым гипогамильтоновым графам, чтобы строить новые того же порядка, и называет Бонди[5]как первоначальный автор метода. В качестве иллюстрации он показывает, что два ребра могут быть добавлены ко второму графу последовательности Линдгрена (которую он называет последовательностью Сусселье), чтобы построить новый гипогамильтонов граф на 16 вершинах. Этот граф называется графом Сусселье.

Рекомендации

  1. ^ Джессика Вольц, Инженерные линейные схемы с SAT. Магистерская работа, Тюбингенский университет, 2018 г.
  2. ^ Сусселье, Р. (1963), Проблем нет. 29: Le cercle des irascibles, 7, Rev. Franç. Речь. Opérationnelle, стр. 405–406.
  3. ^ Линдгрен, В. Ф. (1967), "Бесконечный класс гипогамильтоновых графов", Американский математический ежемесячный журнал, 74: 1087–1089, Дои:10.2307/2313617, МИСТЕР0224501
  4. ^ Herz, J. C .; Duby, J. J .; Виге, Ф. (1967). "Recherche systématique des graphes hypohamiltoniens". Теория графов. Данод. С. 153–159.
  5. ^ В. Хваталь (1973), "Триггеры в гипогамильтоновых графах", Канадский математический бюллетень, 16: 33–41, Дои:10.4153 / cmb-1973-008-9