Клітка (теорія графів)
n-клітка — кубічний граф обхвату n з найменшим можливим числом вершин. Граф називається кубічним, якщо з кожної його вершини виходять 3 ребра. Обхват графа — це довжина найменшого циклу в ньому.
- 3-клітка — К4, остов тетраедра, 4 вершини.
- 4-клітка — К3,3, один з двох мінімальних не планарних графів, 6 вершин.
- 5-клітка — граф Петерсена, 10 вершин. Мінімальний кубічний граф з індексом самоперетину 2.
- 6-клітка — граф Хівуда, 14 вершин. Розбивається на 1-фактори (тобто, реберно розфарбовуємий), будь-яка сума двох чинників утворює гамільтонів цикл. Мінімальний кубічний граф з індексом самоперетину 3.
- 7-клітка — граф Маꥳ, 24 вершини. Мінімальний кубічний граф з індексом самоперетину 8.
- 8-клітка — граф Татта — Коксетера, 30 вершин.
Узагальнене визначення
(r,n)-клітка — регулярний граф ступеня r (тобто з кожної вершини якого виходить рівно r ребер) та обхвату n з найменшим можливим числом вершин.
Тривіальні сімейства
- (2,n)-клітками є, очевидно, циклічні графи Cn
- (r-1,3)-клітки — повні графи Кr з r вершин
- (r,4)-клітки — повні дводольні графи Кr,r, у яких в кожній долі знаходиться по r вершин
Нетривіальні представники
- (7,5)-клітка — граф Гофмана-Сінглтона, 50 вершин.
Відомі ще деякі клітки. У таблиці нижче показано кількість вершин в (r,n)-клітинах ступеня 3≤r≤7 та обхвату 3≤n≤12. Клітки для цих та великих r и n описані тут: (англійською мовою).
| n: | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| r = 3: | 4 | 6 | 10 | 14 | 24 | 30 | 58 | 70 | 112 | 126 |
|---|---|---|---|---|---|---|---|---|---|---|
| r = 4: | 5 | 8 | 19 | 26 | 67 | 80 | 275 | 384 | 728 | |
| r = 5: | 6 | 10 | 30 | 42 | 152 | 170 | 2730 | |||
| r = 6: | 7 | 12 | 40 | 62 | 294 | 312 | 7812 | |||
| r = 7: | 8 | 14 | 50 | 90 | ||||||
Графи Мура
Кількість вершин в (r,n)-клітці більше або дорівнює
- для непарних n та
- для парних.
Якщо має місце рівність, то відповідний граф називається графом Мура. У той час як клітка існує для будь-яких r > 2 і n > 2, нетривіальних графів Мура набагато менше. З вищезгаданих клітин, графами Мура є граф Петерсена, граф Хівуда, граф Татта — Коксетера і граф Гофмана — Синглтона. Доведено,[1][2][3] що всі непарні випадки вичерпуються n = 5, r = 2, 3, 7 та, можливо, 57, а парні n = 6, 8, 12.
Примітки
- Bannai, E. and Ito, T. «On Moore Graphs.» J. Fac. Sci. Univ. Tokyo Ser. A 20, 191—208, 1973
- Damerell, R. M. «On Moore Graphs.» Proc. Cambridge Philos. Soc. 74, 227—236, 1973
- Hoffman, A. J. and Singleton, R. R. «On Moore Graphs of Diameter 2 and 3.» IBM J. Res. Develop. 4, 497—504, 1960
Література
- Ф. Харари Теория графов. — М.: УРСС, — 2003. — 300 с — ISBN 5-354-00301-6.
Посилання
- Biggs, Norman (1993). Algebraic Graph Theory (вид. 2nd). Cambridge Mathematical Library. с. 180–190. ISBN 0-521-45897-8..
- Bollobás, Béla; Szemerédi, Endre (2002). Girth of sparse graphs. Journal of Graph Theory 39 (3): 194–200. MR 1883596. doi:10.1002/jgt.10023..
- Exoo, G; Jajcay, R (2008). Dynamic Cage Survey. Dynamic Surveys. Electronic Journal of Combinatorics DS16. Архів оригіналу за 1 січня 2015. Процитовано 28 червня 2016..
- Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966). On a problem of graph theory. Studia Sci. Math. Hungar. 1: 215–235. Архів оригіналу за 9 березня 2016. Процитовано 28 червня 2016..
- Hartsfield, Nora; Ringel, Gerhard (1990). Pearls in Graph Theory: A Comprehensive Introduction. Academic Press. с. 77–81. ISBN 0-12-328552-6..
- Holton, D. A.; Sheehan, J. (1993). The Petersen Graph. Cambridge University Press. с. 183–213. ISBN 0-521-43594-3..
- Lubotzky, A.; Phillips, R.; Sarnak, P. (1988). Ramanujan graphs. Combinatorica 8 (3): 261–277. MR 963118. doi:10.1007/BF02126799..
- Tutte, W. T. (1947). A family of cubical graphs. Proc. Cambridge Philos. Soc. 43 (4): 459–474. doi:10.1017/S0305004100023720..
Посилання
- Brouwer, Andries E. Cages(англ.)
- Royle, Gordon. Cubic Cages and Higher valency cages(англ.)
- Weisstein, Eric W. Cage Graph(англ.) на сайті Wolfram MathWorld.