Граф Робертсона

Шаблон:Граф Граф Робертсона или (4,5)-клетка — это 4-регулярный неориентированный граф с 19 вершинами и 38 рёбрами, названный именем Шаблон:Не переведено 5Шаблон:RШаблон:R.

Граф Робертсона является уникальной (4,5)-клеткой и его открыл Робертсон в 1964 годуШаблон:R. Как клетка, граф является наименьшим 4-регулярным графом с обхватом 5.

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

Граф Робертсона гамильтонов и он имеет 5376 различных гамильтоновых циклов.

Алгебраические свойства

Граф Робертсона не вершинно-транзитивен и его полная группа автоморфизмов изоморфна диэдральной группе порядка 24, группе симметрий правильного двенадцатиугольника, включая как вращения, так и отраженияШаблон:R.

Характеристический многочлен графа Робертсона равен

$(x-4)(x-1{)}^2(x^2-3{)}^2(x^2+x-5)$

$(x^2+x-4{)}^2(x^2+x-3{)}^2(x^2+x-1).$

Галерея

• 
  Граф Робертсона как он был изображён в оригинальной публикации.
• 
  Хроматическое число графа Робертсона равно 3.
• 
  Хроматический индекс графа Робертсона равен 5.

Ссылки

• M₂₂ graph Шаблон:Wayback at MathWorld