Граф Мередита
Граф Мередита — 4-регулярный неориентированный граф с 70 вершинами и 140 рёбрами, обнаруженный Гаем Мередитом в 1973 году[1].
| Граф Мередита | |
|---|---|
 | |
| Назван в честь | Гая Мередита |
| Вершин | 70 |
| Рёбер | 140 |
| Диаметр | 8 |
| Обхват | 5 |
| Автоморфизмы | 38698352640 |
| Хроматическое число | 3 |
| Хроматический индекс | 5 |
| Свойства | Эйлеров |
| Книжная толщина | 3 |
| Число очередей | 2 |
 Медиафайлы на Викискладе | |
Граф Мередита вершинно 4-связен и рёберно 4-связен. Имеет хроматическое число 3, хроматический индекс 5, радиус 7, диаметр 8, обхват 4 и он не гамильтонов[2]. Граф имеет книжную толщину 3 и число очередей 2[3].
Опубликованный в 1973 году граф представил контрпример гипотезе Криспина Нэша-Уильямса, что любой 4-регулярный вершинно 4-связный граф всегда гамильтонов[4][5]. Тем не менее, Татт показал, что все 4-связные планарные графы гамильтоновы[6].
Характеристический многочлен графа Мередита равен
- .
Галерея
Хроматическое число графа Мередита равно 3.
Хроматический индекс графа Мередита равен 5.
Примечания
- Weisstein, Eric W. Meredith graph (англ.) на сайте Wolfram MathWorld.
- Bondy J. A., Murty U. S. R. Graph Theory. — Springer, 2007. — С. 470.
- Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
- Meredith G. H. J. Regular 4-Valent 4-Connected Nonhamiltonian Non-4-Edge-Colorable Graphs // J. Combin. Th.. — 1973. — Вып. B 14. — С. 55—60.
- Bondy J. A., Murty U. S. R. Graph Theory with Applications. — New York: North Holland, 1976. — С. 239.
- Recent Progress in Combinatorics / Tutte W.ЛитератураT.. — New York: Academic Press, 1969.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.