Граф Сусилье
| Граф Сусилье | |
|---|---|
 | |
| Вершин | 16 |
| Рёбер | 27 |
| Радиус | 2 |
| Диаметр | 3 |
| Обхват | 5 |
| Автоморфизмы | 2 |
| Хроматическое число | 3 |
| Хроматический индекс | 5 |
Граф Сусилье — гипогамильтонов граф с 16 вершинами и 27 рёбрами.
История[править | править код]
Гипогамильтоновы графы первым изучал Сусилье в статье Problèmes plaisants et délectables (1963)[1].
В 1967 Линдгрен построил бесконечную последовательность гипогамильтоновых графов. Все графы этой последовательности имеют 6k+10 вершин для любого целого k[2][3]. Ту же самую последовательность гипогамильтоновых графов независимо построил Сусилье[4]. В 1973 Вацлав Хватал объяснил в научной статье как можно добавить рёбра к некоторому гипогамильтонову графу для построения нового графа этого вида с тем же порядком вершин и указал Бонди[5] автором этого метода. В качестве иллюстрации он показал, что ко второму графу в последовательности Линдгрена можно добавить два ребра (при этом он последовательность называет последовательностью Сусилье) для построения нового гипогамильтонова графа с 16 вершинами. Этот граф был назван графом Сусилье.
Примечания[править | править код]
- ↑ Sousselier, 1963, с. 405–406.
- ↑ Lindgren, 1967, с. 1087–1089.
- ↑ MR: 0224501
- ↑ Herz, Duby, Vigué, 1967, с. 153–159.
- ↑ Chvátal, 1973, с. 33–41.
Литература[править | править код]
- R. Sousselier. Problème no. 29: Le cercle des irascibles // Rev. Franç. Rech. Opérationnelle. — 1963. — Т. 7.
- W. F. Lindgren. An infinite class of hypohamiltonian graphs // American Mathematical Monthly. — 1967. — Т. 74. — P. 1087–1089. — doi:10.2307/2313617.
- J. C. Herz, J. J. Duby, F. Vigué. Recherche systématique des graphes hypohamiltoniens // Theory of Graphs: International Symposium, Rome 1966. — Paris: Gordon and Breach, 1967.
- V. Chvátal. Flip-flops in hypo-Hamiltonian graphs // Canadian Mathematical Bulletin. — 1973. — Т. 16. — P. 33–41.
 | На эту статью не ссылаются другие статьи Википедии. |
| Для улучшения этой статьи желательно:
|