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

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

Граф Биггса — Смита — 3-регулярный граф с 102 вершинами и 153 рёбрами^[1]. Назван в честь Norman Biggs (mathematician) — версия статьи «Биггс, Норман (математик)» на английском языке Биггса (англ.) (рус. и Смита, описавших граф в 1971 году.^[2]

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

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

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

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

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

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

\text{[math]}

(x-3)(x-2)^{18}x^{17}(x^{2}-x-4)^{9}(x^{3}+3x^{2}-3)^{16}

.

ГалереяПравить

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

ПримечанияПравить

↑ Weisstein, Eric W. Biggs–Smith Graph (англ.) на сайте Wolfram MathWorld.
↑ 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
↑ A. E. Brouwer, A. M. Cohen, A. Neumaier. Distance-Regular Graphs.. — New York: Springer-Verlag, 1989.
↑ Royle, G. F102A data (недоступная ссылка)
↑ 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.

[1] Weisstein, Eric W. Biggs–Smith Graph (англ.) на сайте Wolfram MathWorld.

[2] 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] A. E. Brouwer, A. M. Cohen, A. Neumaier. Distance-Regular Graphs.. — New York: Springer-Verlag, 1989.

[4] Royle, G. F102A data (недоступная ссылка)

[5] M. Conder, P. Dobcsányi, «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41-63, 2002.

[6] E. R. van Dam and W. H. Haemers, Spectral Characterizations of Some Distance-Regular Graphs. J. Algebraic Combin. 15, pages 189—202, 2003

[1]

[2]

[3]

[4]

[5]

[6]