Граф Сюселье
| Граф Сюселье | |
|---|---|
 | |
| Вершины | 16 |
| Края | 27 |
| Радиус | 2 |
| Диаметр | 3 |
| Обхват | 5 |
| Автоморфизм | 2 |
| Хроматическое число | 3 |
| Хроматический индекс | 5 |
| Толщина книги | 3 |
| Номер очереди | 2 |
| Таблица графиков и параметров | |
Граф Сусселье в теории графов с представляет собой гипогамильтонов граф 16 вершинами и 27 ребрами. Имеет толщину книги 3 и номер очереди 2. [1]
История
[ редактировать ]Гипогамильтоновы графы были впервые изучены Сусселье в книге «Легкие и восхитительные задачи» (1963).. [2]
В 1967 году Линдгрен строит бесконечную последовательность гипогамильтоновых графов.Все графы этой последовательности имеют 6k +10 вершин для каждого целого числа k . [3] Такую же последовательность гипогамильтоновых графов независимо построил Сусселье. [4] В 1973 году Хватал объясняет в научной статье, как можно добавлять ребра к некоторым гипогамильтоновым графам, чтобы построить новые того же порядка, и называет Бонди [5] как первоначальный автор метода. В качестве иллюстрации он показывает, что ко второму графу последовательности Линдгрена (который он называет последовательностью Сусселье) можно добавить два ребра, чтобы построить новый гипогамильтонов граф на 16 вершинах. Этот граф называется графом Сусселье.
Ссылки
[ редактировать ]- ^ Джессика Вольц, Разработка линейных макетов с помощью SAT . Магистерская диссертация, Тюбингенский университет, 2018 г.
- ^ Сусселье, Р. (1963), Проблема №. 29: Круг раздражительных , т. 7, преп. Франк. Поиск Оперативное, стр. 405–406
- ^ Линдгрен, В. Ф. (1967), «Бесконечный класс гипогамильтоновых графов», American Mathematical Monthly , 74 (9): 1087–1089, doi : 10.2307/2313617 , JSTOR 2313617 , MR 0224501
- ^ Герц, JC; Дуби, Джей-Джей; Виге, Ф. (1967). «Систематический поиск гипогамильтоновых графов». Теория графов . Дюнод. стр. 153–159.
- ^ В. Хватал (1973), «Шлепанцы в гипогамильтоновых графах», Canadian Mathematical Bulletin , 16 : 33–41, doi : 10.4153/cmb-1973-008-9