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

Клітка Фостера, в теорії графів, ще 5-регулярний неорієнтований граф з 30 вершинами та 75 ребрами.[1][2] Він є одним з чотирьох (5,5)-клітинних графів, інші, це граф Мерінгера, граф Робертсона-Вегнера та граф Вонга.

Foster cage
Названий на честь	Рональд Фостер
Вершин	30
Ребер	75
Радіус	3
Діаметр	3
Обхват	5
Автоморфізм	30
Хроматичне число	4
Хроматичний індекс	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. Meringer, Markus (1999). Fast generation of regular graphs and construction of cages. Journal of Graph Theory 30 (2): 137–146. MR 1665972. doi:10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G..