Снарк Секереша

Перейти к навигации Перейти к поиску

Снарк Секереша

Назван в честь	Дьёрдьа Секереша
Вершин	50
Рёбер	75
Хроматическое число	3
Хроматический индекс	4
Свойства	снарк гипогамильтоновый
Медиафайлы на Викискладе

Снарк Секереша — снарк с 50 вершинами и 75 рёбрами^[1], пятый известный снарк. Открыт Дьёрдьем Секерешем в 1973 году^[2].

Как и всякий снарк, является связным кубическим графом без мостов с хроматическим индексом 4. Не является ни планарным, ни гамильтоновым, но при этом гипогамильтонов^[3].

Другой известный снарк с 50 вершинами — снарк Уоткинса, открытый Уоткинсом в 1989 году^[4].

Общие свойства

Максимальный эксцентриситет вершин или диаметр снарка Секереша равен 7. Минимальный эксцентриситет вершин или радиус этого снарка равен 6. Длина самого короткого цикла равна 5. Снарк Секереша является вершинно 3-связным и рёберно 3-связным графом.

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

Группа автоморфизмов снарка Секереша имеет порядок 20.

Характеристический многочлен матрицы смежности снарка Секереша равен

(x-3)(x-1)^{9}(x+2)^{8}(x^{8}-x^{7}-12x^{6}+10x^{5}+41x^{4}-25x^{3}-43x^{2}+13x+6)^{4}

Галерея

Хроматическое число снарка Секереша равно 3.
Хроматический индекс снарка Секереша равен 4.
Альтернативное представление снарка Секереша.

Примечания

↑ Weisstein, Eric W. Szekeres Snark (англ.) на сайте Wolfram MathWorld.
↑ G. Szekeres. Polyhedral decompositions of cubic graphs // Bull. Austral. Math. Soc.. — 1973. — Т. 8, вып. 3. — С. 367–387. — doi:10.1017/S0004972700042660.
↑ Weisstein, Eric W. Hypohamiltonian Graph (англ.) на сайте Wolfram MathWorld.
↑ Watkins, J. J. «Snarks.» Ann. New York Acad. Sci. 576, 606—622, 1989

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

В теории графов графом МакГи, или (3-7)-клеткой, называется 3-регулярный граф с 24 вершинами и 36 рёбрами.

Снарк в теории графов — связный кубический граф без мостов c хроматическим индексом 4. Другими словами, это граф, в котором каждая вершина имеет три соседние вершины и рёбра нельзя выкрасить только в три цвета, так чтобы два ребра одного цвета не сходились в одной вершине. Чтобы избежать тривиальных случаев, снарками часто не считают графы, имеющие обхват меньше 5.

В теории графов снарк Уоткинса — снарк с 50 вершинами и 75 рёбрами. Открыт Джоном Д. Уоткинсом в 1989 году.

Снарк Блануши — 3-регулярный граф с 18 вершинами и 27 рёбрами. Существуют два таких графа. Носят имя нашедшего оба этих графа в 1946 году югославского математика Данило Блануши.

В теории графов снарки «Цветы» образуют бесконечное семейство снарков, введённых Айзексом Руфусом в 1975 году.

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

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

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

В теории графов граф Франклина — это 3-регулярный граф с 12 вершинами и 18 рёбрами.

В теории графов лестница L_n — планарный неориентированный граф с 2n вершинами и n+2(n-1) рёбрами.

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

В теории графов граф Харриса или (3-10)-клетка Харриса — это 3-регулярный неориентированный граф с 70 вершинами и 105 рёбрами.

В теории графов граф Харриса — Вонга — это 3-регулярный неориентированный граф с 70 вершинами и 105 рёбрами.

10-Клетка Балабана или балабанова (3,10)-клетка — это 3-регулярный граф с 70 вершинами и 105 рёбрами, названный именем химика румынского происхождения А.Т. Балабана. Опубликован в 1972. Это была первая обнаруженная (3,10)-клетка, но не единственная.

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

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

Граф Робертсона или (4,5)-клетка — это 4-регулярный неориентированный граф с 19 вершинами и 38 рёбрами, названный именем Нейла Робертсона.

Граф Мередита — 4-регулярный неориентированный граф с 70 вершинами и 140 рёбрами, обнаруженный Гаем Мередитом в 1973 году.

Снарк «двойная звезда» — снарк с 30 вершинами и 45 рёбрами.

Бидиакис-куб — это 3-регулярный граф с 12 вершинами и 18 рёбрами.

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