Снарк Уоткінса
| Снарк Уоткінса | |
|---|---|
 Снарк Уоткінса | |
| Названо на честь | Джона Д. Уоткінса |
| Вершин | 50 |
| Ребер | 75 |
| Радіус | 7 |
| Діаметр | 7 |
| Обхват | 5 |
| Автоморфізм | 5 |
| Хроматичне число | 3 |
| Хроматичний індекс | 4 |
| Властивості | снарк |
Cнарк Уоткінса у теорії графів — це снарк з 50 вершинами та 75 ребрами.[1][2] Він був винайдений Джоном Уоткінсом у 1989 році.[3]
Як снарк, граф Уоткінса з'єднує кубічний граф без мостів з хроматичним індексом, який дорівнює 4. Снарк Уоткінса також є непланарним та негамільтоновим графом.
Снарк Секереша — це не менш відомий снарк з 50 вершинами, п'ятий найвідоміший снарк, винайдений Дьйордем Секерешем у 1973.[4]
Галерея
-
Хроматичне число снарка Уоткінса дорівнює 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]]
Примітки
- ↑ Weisstein, Eric W. Watkins Snark(англ.) на сайті Wolfram MathWorld.
- ↑ 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 A. J. Schwenk). New York: Wiley, pp. 1129—1144, 1991
- ↑ Watkins, J. J. «Snarks.» Ann. New York Acad. Sci. 576, 606—622, 1989.
- ↑ Джордж Серкеш. Поліетрадні розбиття кубічних графів // 03. — Bull. Austral. Math. Soc., 1973. — Т. 8. — С. 367–387. — DOI:.