Снарк Секереша (Vugjt Vytyjyog)

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

снарк


гипогамильтоновый
Логотип Викисклада Медиафайлы на Викискладе

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

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

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

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

[править | править код]

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

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

[править | править код]

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

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

.

Примечания

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