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

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

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

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

Снарк Секереша — це не менш відомий снарк з 50 вершинами, п'ятий найвідоміший снарк, винайдений Дьйордем Секерешем у 1973.[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 A. J. Schwenk). 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.