Граф Мередита

Граф Мередита — 4-регулярный неориентированный граф с 70 вершинами и 140 рёбрами, обнаруженный Гаем Мередитом в 1973 году.

Граф Мередита вершинно 4-связен и рёберно 4-связен. Имеет хроматическое число 3, хроматический индекс 5, радиус 7, диаметр 8, обхват 4 и он не гамильтоновШаблон:R. Граф имеет книжную толщину 3 и число очередей 2Шаблон:R.

Опубликованный в 1973 году граф представил контрпример гипотезе Криспина Нэша-Уильямса, что любой 4-регулярный вершинно 4-связный граф всегда гамильтоновШаблон:RШаблон:R. Тем не менее, Татт показал, что все 4-связные планарные графы гамильтоновыШаблон:R.

Шаблон:Clear Характеристический многочлен графа Мередита равен

$(x-4)(x-1{)}^{10}{x}^{21}(x+1{)}^{11}(x+3)(x^2-13)(x^6-26x^4+3x^3+169x^2-39x-45{)}^4$.

Галерея

• 
  Хроматическое число графа Мередита равно 3.
• 
  Хроматический индекс графа Мередита равен 5.

Ссылки

• A.E. Brouwer’s website: The Armanios-Wells graph Шаблон:Wayback