Граф Вонга

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

Граф Вонга
Граф Вонга
Назван в честь	Pak-Ken Wong
Вершин	30
Рёбер	75
Диаметр	3
Обхват	5
Автоморфизмы	96
Хроматическое число	4
Хроматический индекс	5
Свойства	Клетка

Подобно (не связанному с этим графом) графу Харриса — Вонга, граф назван именем Пака-Кена Вонга[3].

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

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

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

(x-5)(x+1)^{2}(x^{2}-5)^{3}(x-1)^{5}(x^{2}+x-5)^{8}.

Литература

Weisstein, Eric W. Wong Graph (англ.) на сайте Wolfram MathWorld.
Markus Meringer. Fast generation of regular graphs and construction of cages // Journal of Graph Theory. — 1999. — Т. 30, вып. 2. — С. 137–146. — doi:10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G.
Wong P. K. Cages--A Survey // J. Graph Th.. — 1982. — Вып. 6. — С. 1-22.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.