Клетка Фостера

Клетка Фостера
Полная раскраска клетки Фостера
Назван в честь	Рональда Фостера
Вершин	30
Рёбер	75
Диаметр	3
Обхват	5
Автоморфизмы	30
Хроматическое число	4
Хроматический индекс	5
Свойства	Клетка

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

Подобно не связанному с этим графом графу Фостера, клетка названа именем Рональда Фостера.

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

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

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

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

Примечания

1. Weisstein, Eric W. Foster Cage (англ.) на сайте Wolfram MathWorld.
2. 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.