Граф Мередита — 4-регулярный неориентированный граф с 70 вершинами и 140 рёбрами, обнаруженный Гаем Мередитом в 1973 году.
Граф Мередита вершинно 4-связен и рёберно 4-связен. Имеет хроматическое число 3, хроматический индекс 5, радиус 7, диаметр 8, обхват 4 и он не гамильтонов. Граф имеет книжную толщину 3 и число очередей 2.
Опубликованный в 1973 году граф представил контрпример гипотезе Криспина Нэша-Уильямса, что любой 4-регулярный вершинно 4-связный граф всегда гамильтонов. Тем не менее, Татт показал, что все 4-связные планарные графы гамильтоновы.
Характеристический многочлен графа Мередита равен .
Галерея
Примечания
Ссылки A.E. Brouwer’s website: The Armanios-Wells graph
Категория:Регулярные графы Категория:Графы, имеющие собственные названия