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

Граф Биггса — Смита — 3-регулярный граф с 102 вершинами и 153 рёбрами. Назван в честь Биггса и Смита, описавших граф в 1971 году.Biggs, N. L., & Smith, D. H. (1971). On Trivalent Graphs. Bulletin of the London Mathematical Society, 3(2), 155–158. doi:10.1112/blms/3.2.155

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

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

Алгебраические свойства Группа автоморфизмов графа Биггса — Смита — это группа порядка 2448Royle, G. F102A data, изоморфная группе проективной группе PSL(2,17). Она действует транзитивно на вершины и рёбра графа, поэтому граф Биггса — Смита является симметричным. Граф имеет автоморфизмы, которые переводят любую вершину в любую другую и любое ребро в любое другое ребро. В списке Фостера граф Биггса — Смита, указанный как F102A, является единственным симметричным графом с 102 вершинамиM. Conder, P. Dobcsányi, «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41-63, 2002..

Граф Биггса — Смита однозначно определяется по его спектру, множеству собственных значений матрицы смежности графаE. R. van Dam and W. H. Haemers, Spectral Characterizations of Some Distance-Regular Graphs. J. Algebraic Combin. 15, pages 189—202, 2003.

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

Галерея

Примечания

Литература On trivalent graphs, NL Biggs, DH Smith — Bulletin of the London Mathematical Society, 3 (1971) 155—158.

Категория:Регулярные графы Категория:Графы, имеющие собственные названия