Снарк Уоткінса

Снарк Уоткінса у теорії графів — це снарк з 50 вершинами та 75 ребрами. Він був винайдений Джоном Уоткінсом у 1989 році.

Снарк Уоткінса
Снарк Уоткінса
Названо на честь	Джона Д. Уоткінса
(Вершин)	50
(Ребер)	75
(Радіус)	7
(Діаметр)	7
(Обхват)	5
(Автоморфізм)	5
Хроматичне число	3
Хроматичний індекс	4
Число черг	2
Властивості	снарк

Як снарк, граф Уоткінса з'єднує кубічний граф без мостів з хроматичним індексом, який дорівнює 4. Снарк Уоткінса також є непланарним та негамільтоновим графом.

Снарк Секереша — це не менш відомий снарк з 50 вершинами, п'ятий найвідоміший снарк, винайдений Дьйордем Секерешем у 1973.

Галерея

• Хроматичне число снарка Уоткінса дорівнює 3.
• Хроматичний індекс снарка Уоткінса дорівнює 4.

Вершини

[[1,2], [1,4], [1,15], [2,3], [2,8], [3,6], [3,37], [4,6], [4,7], [5,10], [5,11], [5,22], [6,9], [7,8], [7,12], [8,9], [9,14], [10,13], [10,17], [11,16], [11,18], [12,14], [12,33], [13,15], [13,16], [14,20], [15,21], [16,19], [17,18], [17,19], [18,30], [19,21], [20,24], [20,26], [21,50], [22,23], [22,27], [23,24], [23,25], [24,29], [25,26], [25,28], [26,31], [27,28], [27,48], [28,29], [29,31], [30,32], [30,36], [31,36], [32,34], [32,35], [33,34], [33,40], [34,41], [35,38], [35,40], [36,38], [37,39], [37,42], [38,41], [39,44], [39,46], [40,46], [41,46], [42,43], [42,45], [43,44], [43,49], [44,47], [45,47], [45,48], [47,50], [48,49], [49,50]]

Примітки

1. Weisstein, Eric W. Watkins Snark(англ.) на сайті Wolfram MathWorld.
2. Watkins, J. J. and Wilson, R. J. «A Survey of Snarks.» In Graph Theory, Combinatorics, and Applications (Ed. Y. Alavi, G. Chartrand, O. R. Oellermann, and ). New York: Wiley, pp. 1129—1144, 1991
3. Watkins, J. J. «Snarks.» Ann. New York Acad. Sci. 576, 606—622, 1989.
4. Джордж Серкеш. Поліетрадні розбиття кубічних графів // 03. — Bull. Austral. Math. Soc., 1973. — Т. 8. — С. 367–387. — DOI:10.1017/S0004972700042660.