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

Перейти к навигации Перейти к поиску

Граф Робертсона
Граф Робертсона гамильтонов
Назван в честь	Нейла Робертсона^[англ.]
Вершин	19
Рёбер	38
Диаметр	3
Обхват	5
Автоморфизмы	24 (D₁₂)
Хроматическое число	3
Хроматический индекс	5^[1]
Свойства	Клетка Гамильтонов
Книжная толщина	3
Число очередей	2
Медиафайлы на Викискладе

Граф Робертсона или (4,5)-клетка — это 4-регулярный неориентированный граф с 19 вершинами и 38 рёбрами, названный именем Нейла Робертсона^[англ.]^[2]^[3].

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

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

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

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

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

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

(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.

Литература

↑ Weisstein, Eric W. Class 2 Graph (англ.) на сайте Wolfram MathWorld.
↑ Weisstein, Eric W. Robertson Graph (англ.) на сайте Wolfram MathWorld.
↑ Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.
↑ Robertson, N. "The Smallest Graph of Girth 5 and Valency 4." Bull. Amer. Math. Soc. 70, 824-825, 1964.
↑ Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
↑ Geoffrey Exoo & Robert Jajcay, Dynamic cage survey, Electr. J. Combin. 15, 2008.

Ссылки

M₂₂ graph Архивная копия от 18 февраля 2019 на Wayback Machine at MathWorld

Похожие исследовательские статьи

В теории графов треугольным графом называется планарный неориентированный граф с тремя вершинами и тремя рёбрами, образующими треугольник.

В теории графов графом МакГи, или (3-7)-клеткой, называется 3-регулярный граф с 24 вершинами и 36 рёбрами.

Граф Дика — 3-регулярный граф с 32 вершинами и 48 рёбрами, назван в честь Вальтера фон Дика .

Снарк Секереша — снарк с 50 вершинами и 75 рёбрами, пятый известный снарк. Открыт Дьёрдьем Секерешем в 1973 году.

Граф Биггса — Смита — 3-регулярный граф с 102 вершинами и 153 рёбрами. Назван в честь Биггса и Смита, описавших граф в 1971 году.

Граф Коксетера — 3-регулярный граф с 28 вершинами и 42 рёбрам Все кубические дистанционно-регулярные графы известны, граф Коксетера — один из 13-ти таких графов.

В теории графов граф Франклина — это 3-регулярный граф с 12 вершинами и 18 рёбрами.

Граф F26A — симметричный двудольный кубический граф с 26 вершинами и 39 рёбрами.

В теории графов граф Харриса или (3-10)-клетка Харриса — это 3-регулярный неориентированный граф с 70 вершинами и 105 рёбрами.

В теории графов граф Харриса — Вонга — это 3-регулярный неориентированный граф с 70 вершинами и 105 рёбрами.

10-Клетка Балабана или балабанова (3,10)-клетка — это 3-регулярный граф с 70 вершинами и 105 рёбрами, названный именем химика румынского происхождения А.Т. Балабана. Опубликован в 1972. Это была первая обнаруженная (3,10)-клетка, но не единственная.

Граф Фолкмана — это двудольный 4-регулярный граф с 20 вершинами и 40 рёбрами.

11-клетка Балабана или (3-11)-клетка Балабана — это 3-регулярный граф с 112 вершинами и 168 рёбрами, названные именем румынского химика Александру Т. Балабана.

Граф Хоффмана является 4-регулярным графом с 16 вершинами и 32 рёбрами, который открыл Алан Хоффман и опубликовал в 1963. Граф коспектрален графу гиперкуба Q₄.

Граф Робертсона — Вегнера — 5-регулярный неориентированный граф с 30 вершинами и 75 рёбрами, названный именами Нейла Робертсона и Дж. Вегнера.

Граф Вонга — 5-регулярный неориентированный граф с 30 вершинами и 75 рёбрами. Граф является одной из четырёх (5,5)-клеток, другие три — клетка Фостера, граф Мерингера и граф Робертсона — Вегнера.

Граф Мерингера — 5-регулярный неориентированный граф с 30 вершинами и 75 рёбрами. Граф является одной из четырёх (5,5)-клеток, другие три — клетка Фостера, граф Робертсона — Вегнера и граф Вонга. Граф назван именем Маркуса Мерингера, открывшего его в 1999, хотя он долгое время считал, что только три подобных графа существует.

Клетка Фостера — 5-регулярный неориентированный граф с 30 вершинами и 75 рёбрами. Граф является одной из четырёх (5,5)-клеток, другие три: граф Мерингера, граф Робертсона — Вегнера и граф Вонга.

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

Бидиакис-куб — это 3-регулярный граф с 12 вершинами и 18 рёбрами.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.