WikiSort.ru - Не сортированное

Граф Бигса–Смита
Вершин	102
Рёбер	153
Радиус	7
Диаметр	7
Обхват	9
Автоморфизмы	2448 (PSL(2,17))
Хроматическое число	3
Хроматический индекс	3
Свойства	кубический симметричный гамильтонов дистанционно-регулярный

Граф Бигса — Смита — 3-регулярный граф с 102 вершинами и 153 рёбрами^[1].

Хроматическое число графа равно 3, хроматический индекс равен 3, радиус равен 7, диаметр — 7, а обхват — 9. Граф является также вершинно 3-связным и рёберно 3-связным.

Все кубические дистанционно-регулярные графы известны^[2], граф Бигса — Смита — один из 13-ти таких графов.

Алгебраические свойства

Группа автоморфизмов графа Бигса — Смита — это группа порядка 2448^[3], изоморфная группе проективной группе PSL(2,17). Она действует транзитивно на вершины и рёбра графа, поэтому граф Бигса — Смита является симметричным. Граф имеет автоморфизмы, которые переводят любую вершину в любую другую и любое ребро в любое другое ребро. В списке Фостера граф Бигса — Смита, указанный как F102A, является единственным симметричным графом с 102 вершинами^[4].

Граф Бигса — Смита однозначно определяется по его спектру, множеству собственных значений матрицы смежности графа^[5].

Характеристический многочлен графа Бигса — Смита равен:

${\displaystyle (x-3)(x-2)^{18}x^{17}(x^{2}-x-4)^{9}(x^{3}+3x^{2}-3)^{16}}$ .

Галерея

• 
  Хроматическое число графа Бигса — Смита равно 3.
• 
  Хроматический индекс графа Бигса — Смита равен 3.
• 
  Альтернативное графическое представление графа Бигса — Смита.
• 
  Разложение графа Бигса — Смита на 6 множеств по 17 элементов в каждом.

Примечания

Литература

• On trivalent graphs, NL Biggs, DH Smith — Bulletin of the London Mathematical Society, 3 (1971) 155—158.