06-05-2024
Граф Фостера | |
Назван в честь | |
---|---|
Вершин |
90 |
Рёбер |
135 |
Радиус |
8 |
Диаметр |
8 |
Обхват |
10 |
Автоморфизмы |
4320 |
Хроматическое число |
2 |
Хроматический индекс |
3 |
Свойства |
кубический |
Граф Фостера — это двудольный 3-регулярный граф с 90 вершинами и 135 рёбрами[1]. Граф Фостера является гамильтоновым, имеет хроматическое число 2, хроматический индекс 3, радиус 8, диаметр 8 и обхват 10. Он также является вершинно 3-связным и рёберно 3-связным.
Все кубические дистанционно-регулярные графы известны.[2] Граф Фостера — один из 13 таких графов. Граф является единственным дистанционно-транзитивным графом с массивом пересечений {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}.[3] Граф можно построить как граф инциденций частично линейного пространства[en], которое является единственным тройным накрытием без восьмиугольников обобщённых четырёхугольников[en] GQ(2,2). Граф назван в честь Рональда Мартина Фостера[en], составивших список кубических симметричных графов (список Фостера), который включает граф Фостера.
Группа автоморфизмов графа Фостера — это группа порядка 4320.[4] Она действует транзитивно на вершины и рёбра графа, поэтому граф Фостера является симметричным. Граф имеет автоморфизмы, которые переводят любую вершину в любую другую и любое ребро в любое другое ребро. В списке Фостера граф Фостера, указанный как F90A, является единственным кубическим симметричным графом с 90 вершинами.[5]
Характеристический многочлен графа Фостера равен .
Граф Фостера, раскрашенный таким образом, чтобы выделить различные циклы.
Хроматическое число графа Фостера равно 2.
Хроматический индекс графа Фостера равен 3.
Дэвида фостера уоллеса, аналог фостера, foster 033643, тюльпаны фостера.