В математической области теории графов , то граф Биггс-Смит является 3- регулярного графа с вершинами 102 и 153 ребер. [1]
График Биггса – Смита | |
---|---|
Вершины | 102 |
Края | 153 |
Радиус | 7 |
Диаметр | 7 |
Обхват | 9 |
Автоморфизмы | 2448 ( PSL (2,17)) |
Хроматическое число | 3 |
Хроматический индекс | 3 |
Характеристики | Симметричный дистанционно-регулярный кубический гамильтониан |
Таблица графиков и параметров |
Он имеет хроматическое число 3, хроматический индекс 3, радиус 7, диаметр 7 и обхват 9. Это также граф с 3 связями по вершинам и граф с 3 связями по ребрам .
Все кубические дистанционно регулярные графы известны. [2] Граф Биггса – Смита - один из 13 таких графов.
Алгебраические свойства
Группа автоморфизмов графа Биггса – Смита - это группа порядка 2448 [3], изоморфная проективной специальной линейной группе PSL (2,17). Он действует транзитивно на вершинах, на ребрах и на дугах графа. Следовательно, граф Биггса – Смита является симметричным графом . У него есть автоморфизмы, которые переводят любую вершину в любую другую вершину и любое ребро в любое другое ребро. Согласно переписи населения Фостера , граф Биггса – Смита, обозначенный как F102A, является единственным кубическим симметричным графом с 102 вершинами. [4]
Граф Биггса – Смита также однозначно определяется своим спектром графа , набором собственных значений графа его матрицы смежности . [5]
Характеристический полином графа Биггс-Смит:.
Галерея
Хроматического числа графа Биггс-Смита равен 3.
Хроматической индекс графа Биггс-Смита равен 3.
Альтернативный рисунок графа Биггса – Смита.
Рекомендации
- ^ Вайсштейн, Эрик В. "График Биггса-Смита" . MathWorld .
- ^ Брауэр, AE ; Коэн, AM; и Ноймайер А. Дистанционно регулярные графы. Нью-Йорк: Springer-Verlag, 1989.
- ^ Ройл, Г. Данные F102A [ постоянная мертвая ссылка ]
- ^ Кондер, М. и Добчаньи, П. "Трехвалентные симметричные графы до 768 вершин". J. Combin. Математика. Комбинировать. Comput. 40, 41–63, 2002.
- ^ ER ван Дам и WH Хемерс, Спектральные характеристики некоторых дистанционно регулярных графов. J. Алгебраический комбинат. 15, страницы 189–202, 2003 г.
- О трехвалентных графах, Н.Л. Биггс, Д.Х. Смит - Бюллетень Лондонского математического общества, 3 (1971) 155-158.