Меню
Главная
Случайная статья
Настройки
|
Граф Мередита — 4-регулярный неориентированный граф с 70 вершинами и 140 рёбрами, обнаруженный Гаем Мередитом в 1973 году[1].
Граф Мередита вершинно 4-связен и рёберно 4-связен. Имеет хроматическое число 3, хроматический индекс 5, радиус 7, диаметр 8, обхват 4 и он не гамильтонов[2]. Граф имеет книжную толщину 3 и число очередей 2[3].
Опубликованный в 1973 году граф представил контрпример гипотезе Криспина Нэша-Уильямса, что любой 4-регулярный вершинно 4-связный граф всегда гамильтонов[4][5]. Тем не менее, Татт показал, что все 4-связные планарные графы гамильтоновы[6].
Характеристический многочлен графа Мередита равен
- .
Галерея
Примечания
- 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 Tbingen, 2018
- Meredith G. H. J. Regular 4-Valent 4-Connected Nonhamiltonian Non-4-Edge-Colorable Graphs // J. Combin. Th.. — 1973. — Вып. B 14. — С. 55—60.
-
-
Ссылки
|
|
