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

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

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

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

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

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

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

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

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

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

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

Похожие исследовательские статьи

В теории графов нечётные графы O_n — это семейство симметричных графов с высоким нечётным обхватом, определённых на некоторых семействах множеств. Они включают и обобщают графы Петерсена.

Граф Хивуда — ненаправленный граф с 14 вершинами и 21 ребром, названный в честь Перси Джона Хивуда.

Симметричный граф (или транзитивный относительно дуг граф) — граф G, для любых двух пар смежных вершин которого u₁—v₁ и u₂—v₂ имеется автоморфизм:

f : V(G) → V(G)

<span class="mw-page-title-main">Дистанционно-транзитивный граф</span> такой граф, что для любых двух заданных вершин v и w, находящихся на расстоянии i, и любых двух вершин x и y, находящихся на том же расстоянии, су

Дистанционно-транзитивный граф — граф, в котором любая упорядоченная пара вершин переводится в любую другую упорядоченную пару вершин с тем же расстоянием между вершинами одним из автоморфизмов графа.

<span class="mw-page-title-main">Граф Дезарга</span> дистанционно-транзитивный кубический граф с 20 вершинами и 30 рёбрами

Граф Дезарга — дистанционно-транзитивный кубический граф с 20 вершинами и 30 рёбрами. Назван в честь Жерара Дезарга. Возникает в некоторых комбинаторных построениях, имеет высокую степень симметрии, это единственный известный непланарный кубический частичный куб и применяется в химических базах данных.

Граф Мёбиуса — Кантора — симметричный двудольный кубический граф с 16 вершинами и 24 рёбрами, названный в честь Августа Фердинанда Мёбиуса и Зелигмана Кантора (1857—1903). Его можно определить как обобщённый граф Петерсена $\text{[math]}$ , то есть он образован вершинами восьмиугольника, соединёнными с восьмиугольной звездой, в которой каждая точка соединена с третьей по счёту точкой.

В теории графов графом Паппа называется двудольный 3-регулярный неориентированный граф с 18 вершинами и 27 рёбрами, являющийся графом Леви конфигурации Паппа. Он назван в честь Паппа Александрийского, математика Древней Греции, который верил, что доказал «теорему о шестиугольнике», в которой описывал конфигурацию Паппа. Все кубические дистанционно-регулярные графы известны. Граф Паппа — один из тринадцати таких графов.

Граф Грея — двудольный неориентированный граф с 54 вершинами и 81 рёбрами. Граф является кубическим — любая вершина принадлежит ровно трём рёбрам. Граф был открыт Греем в 1932 году, затем открыт независимо Баувером (Bouwer) в 1968 году в ответ на вопрос, поставленный Фолкманом в 1967 году. Граф Грея примечателен как исторически первый пример кубического графа, имеющего алгебраическое свойство рёберной, но не вершинной транзитивности.

Граф Дика — 3-регулярный граф с 32 вершинами и 48 рёбрами, назван в честь Вальтера фон Дика .

Граф Фостера — двудольный 3-регулярный граф с 90 вершинами и 135 рёбрами. Граф Фостера является гамильтоновым, имеет хроматическое число 2, хроматический индекс 3, радиус 8, диаметр 8 и обхват 10. Также является вершинно 3-связным и рёберно 3-связным.

Граф Коксетера — 3-регулярный граф с 28 вершинами и 42 рёбрам Все кубические дистанционно-регулярные графы известны, граф Коксетера — один из 13-ти таких графов.

В теории графов граф Науру — это симметричный двудольный кубический граф с 24 вершинами и 36 рёбрами. Граф был назван Дэвидом Эпштейном по аналогии с двенадцатилучевой звездой на флаге Науру.

Граф F26A — симметричный двудольный кубический граф с 26 вершинами и 39 рёбрами.

Граф Хортона — 3-регулярный граф с 96 вершинами и 144 рёбрами, открытый Джозефом Хортоном. Бонди и Мурти опубликовали в 1976 этот граф в качестве контрпримера гипотезе Татта, что любой кубический 3-связный двудольный граф является гамильтоновым.

12-клетка Татта — 3-регулярный граф с 126 вершинами и 189 рёбрами, названный в честь Уильяма Татта.

Граф Фолкмана — это двудольный 4-регулярный граф с 20 вершинами и 40 рёбрами.

11-клетка Балабана или (3-11)-клетка Балабана — это 3-регулярный граф с 112 вершинами и 168 рёбрами, названные именем румынского химика Александру Т. Балабана.

Граф Хоффмана является 4-регулярным графом с 16 вершинами и 32 рёбрами, который открыл Алан Хоффман и опубликовал в 1963. Граф коспектрален графу гиперкуба Q₄.

3-регулярный граф Клейна — кубический граф с 56 вершинами и 84 рёбрами; назван по имени Феликса Клейна с двойственным ему 7-регулярным графом.

7-регулярный граф Клейна — регулярный граф степени 7 с 24 вершинами и 84 рёбрами; назван, наряду с двойственным ему 3-регулярным графом, по имени Феликса Клейна.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.