Граф Фостера — двудольный 3-регулярный граф с 90 вершинами и 135 рёбрами. Граф Фостера является гамильтоновым, имеет хроматическое число 2, хроматический индекс 3, радиус 8, диаметр 8 и обхват 10. Также является вершинно 3-связным и рёберно 3-связным.
Все кубические дистанционно-регулярные графы известны, граф Фостера — один из 13 таких графов. Граф является единственным дистанционно-транзитивным графом с массивом пересечений {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}Cubic distance-regular graphs , A. Brouwer.. Граф можно построить как граф инциденций , которое является единственным тройным накрытием без восьмиугольников обобщённых четырёхугольников GQ (2,2). Граф назван в честь Рональда Фостера, составившего список кубических симметричных графов (список Фостера), который включает граф Фостера.
Алгебраические свойства Группа автоморфизмов графа Фостера — это группа порядка 4320Royle, G. F090A data. Она действует транзитивно на вершины и рёбра графа, поэтому граф Фостера является симметричным. Граф имеет автоморфизмы, которые переводят любую вершину в любую другую и любое ребро в любое другое ребро. В списке Фостера граф Фостера, указанный как F90A, является единственным кубическим симметричным графом с 90 вершинамиM. Conder, P. Dobcsányi, «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41—63, 2002..
Характеристический многочлен графа Фостера равен .
Галерея
Примечания
Литература
Категория:Регулярные графы Категория:Графы, имеющие собственные названия