Граф Биггса — Смита

Граф Биггса — Смита — 3-регулярный граф с 102 вершинами и 153 рёбрами. Назван в честь Биггса и Смита, описавших граф в 1971 году.

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

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

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

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

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

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

$(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.