Граф Робертсона — Вегнера

Граф Робертсона — Вегнера
Назван в честь	Нейла Робертсона^[англ.] и Дж. Вегнера
Вершин	30
Рёбер	75
Диаметр	3
Обхват	5
Автоморфизмы	20
Хроматическое число	4
Хроматический индекс	5[1]
Свойства	Клетка

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

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

Граф имеет хроматическое число 4, диаметр 3 и он вершинно 5-связен.

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

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

${\displaystyle (x-5)(x-2)^{8}(x+1)(x+3)^{4}(x^{4}+2x^{3}-4x^{2}-5x+5)^{2}(x^{4}+2x^{3}-6x^{2}-7x+11)^{2}.}$

Литература

1. Weisstein, Eric W. Class 2 Graph (англ.) на сайте Wolfram MathWorld.
2. Weisstein, Eric W. Robertson–Wegner Graph (англ.) на сайте Wolfram MathWorld.
3. Bondy J. A., Murty U. S. R. Graph Theory with Applications. — New York: North Holland, 1976. — С. 238.
4. Wong P. K. A note on a paper of G. Wegner // Journal of Combinatorial Theory. — 1977. — Июнь (вып. 22:3). — С. 302-303. — doi:10.1016/0095-8956(77)90081-8.