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

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

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

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

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

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

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

Литература
  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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.