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

Снарк Секереша — снарк с 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}

.

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.