В математической области теории графов , то граф Фостера является двудольным 3- регулярного графа с 90 вершинами и ребрами 135. [1]
Граф Фостера | |
---|---|
Названный в честь | Рональд Мартин Фостер |
Вершины | 90 |
Края | 135 |
Радиус | 8 |
Диаметр | 8 |
Обхват | 10 |
Автоморфизмы | 4320 |
Хроматическое число | 2 |
Хроматический индекс | 3 |
Номер очереди | 2 |
Характеристики | Кубический двудольный симметричный гамильтониан, дистанционно-транзитивный |
Таблица графиков и параметров |
Граф Фостера является гамильтоновым и имеет хроматическое число 2, хроматический индекс 3, радиус 8, диаметр 8 и обхват 10. Он также является трехвершинно -связным и трехреберно -связным графом. У него очередь номер 2, а верхняя граница толщины книги - 4. [2]
Все кубические дистанционно регулярные графы известны. [3] Граф Фостера - один из 13 таких графов. Это единственный дистанционно-транзитивный граф с массивом пересечений {3,2,2,2,2,1,1,1; 1,1,1,1,2,2,2,3}. [4] Она может быть построена как инцидентности графа из частичного линейного пространства , которая является уникальной тройной крышкой , без 8-угольников обобщенного четырехугольника GQ (2,2) . Она названа в честь Р. Фостер , которого Фостер Перепись из кубических симметричных графов включила этот график.
Двудольный половина графа Фостера является дистанционно регулярным графом и локально линейным граф . Это один из конечного числа таких графов шестой степени. [5]
Алгебраические свойства
Группа автоморфизмов графа Фостера - это группа порядка 4320. [6] Она действует транзитивно на вершинах, на ребрах и на дугах графа. Следовательно, граф Фостера является симметричным графом . У него есть автоморфизмы, которые переводят любую вершину в любую другую вершину и любое ребро в любое другое ребро. Согласно переписи населения Фостера, граф Фостера, обозначенный как F90A, является единственным кубическим симметричным графом с 90 вершинами. [7]
Характеристический полином графа Foster равен.
Галерея
График Фостера раскрашен для выделения различных циклов.
Хроматического числа графа Foster 2.
Хроматической индекс графа Foster равен 3.
Рекомендации
- ^ Вайсштейн, Эрик В. "График Фостера" . MathWorld .
- ^ Wolz, Джессика; Инженерные линейные схемы с SAT. Магистерская работа, Тюбингенский университет, 2018 г.
- ^ Брауэр, AE; Коэн, AM; и Ноймайер А. Дистанционно регулярные графы. Нью-Йорк: Springer-Verlag, 1989.
- ^ Кубические дистанционно регулярные графы , А. Брауэр.
- ^ Хираки, Акира; Номура, Казумаса; Судзуки, Хироши (2000), "Дистанционно регулярные графы валентности 6 и», Журнал алгебраической комбинаторике , 11 (2): 101-134, DOI : 10.1023 / A: 1008776031839 , MR 1761910
- ^ Ройл, Г. Данные F090A [ постоянная мертвая ссылка ]
- ^ Кондер, М. и Добчаньи, П. "Трехвалентные симметричные графы до 768 вершин". J. Combin. Математика. Комбинировать. Comput. 40, 41-63, 2002.
- Биггс, Нидерланды; Boshier, AG; Shawe-Тейлор, Дж (1986), "Кубические дистанционно регулярных графов", журнал Лондонского математического общества , 33 (3): 385-394, DOI : 10,1112 / jlms / s2-33.3.385 , МР 0850954.
- Ван Дам, Эдвин Р .; Haemers, Willem H. (2002), " О спектральных характеристиках некоторых дистанционно регулярных графов", журнал алгебраической комбинаторики , 15 (2): 189-202, DOI : 10.1023 / A: 1013847004932 , MR 1887234.
- Ван Maldeghem, Хендрик (2002), "Десять исключительной геометрия из трехвалентного расстояния регулярных графов", Анналы Комбинаторики , 6 (2): 209-228, DOI : 10.1007 / PL00012587 , МР 1955521.