У Вікіпедії є статті про інші значення цього терміна n клітка кубічний граф обхвату n з найменшим можливим числом вершин

У Вікіпедії є статті про інші значення цього терміна: .

n-клітка — кубічний граф обхвату n з найменшим можливим числом вершин. Граф називається кубічним, якщо з кожної його вершини виходять 3 ребра. Обхват графа — це довжина найменшого циклу в ньому.

3-клітка — К₄, остов тетраедра, 4 вершини.
4-клітка — К_3,3, один з двох мінімальних не планарних графів, 6 вершин.
5-клітка — граф Петерсена, 10 вершин. Мінімальний кубічний граф з індексом самоперетину 2.
6-клітка — граф Хівуда, 14 вершин. Розбивається на 1-фактори (тобто, реберно розфарбовуємий), будь-яка сума двох чинників утворює гамільтонів цикл. Мінімальний кубічний граф з індексом самоперетину 3.
7-клітка — граф МакҐі, 24 вершини. Мінімальний кубічний граф з індексом самоперетину 8.
8-клітка — граф Татта — Коксетера, 30 вершин.

Узагальнене визначення

(r,n)-клітка — регулярний граф ступеня r (тобто з кожної вершини якого виходить рівно r ребер) та обхвату n з найменшим можливим числом вершин.

Тривіальні сімейства

(2,n)-клітками є, очевидно, циклічні графи C_n
(r-1,3)-клітки — повні графи К_r з r вершин
(r,4)-клітки — повні двочасткові графи К_r,r, у яких в кожній долі знаходиться по r вершин

Нетривіальні представники

(7,5)-клітка — граф Гофмана — Синглтона, 50 вершин.

Відомі ще деякі клітки. У таблиці нижче показано кількість вершин в (r,n)-клітинах ступеня 3≤r≤7 та обхвату 3≤n≤12. Клітки для цих та великих r и n описані тут: (англійською мовою).

r = 3:	4	6	10	14	24	30	58	70	112	126
n:	3	4	5	6	7	8	9	10	11	12
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)-клітці більше або дорівнює

1+r\sum _{i=0}^{(n-3)/2}(r-1)^{i}

для непарних n та

2\sum _{i=0}^{(n-2)/2}(r-1)^{i}

для парних.

Якщо має місце рівність, то відповідний граф називається графом Мура. У той час як клітка існує для будь-яких r > 2 і n > 2, нетривіальних графів Мура набагато менше. З вищезгаданих клітин, графами Мура є граф Петерсена, граф Хівуда, граф Татта — Коксетера і граф Гофмана — Синглтона. Доведено, що всі непарні випадки вичерпуються 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 с — .

Посилання

(1993), Algebraic Graph Theory (вид. 2nd), Cambridge Mathematical Library, с. 180—190, ISBN .
; Szemerédi, Endre (2002), Girth of sparse graphs, , 39 (3): 194—200, doi:10.1002/jgt.10023, MR 1883596.
Exoo, G; Jajcay, R (2008), , Dynamic Surveys, , DS16, архів оригіналу за 1 січня 2015, процитовано 28 червня 2016.
Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), (PDF), Studia Sci. Math. Hungar., 1: 215—235, архів оригіналу (PDF) за 9 березня 2016, процитовано 28 червня 2016.
; (1990), Pearls in Graph Theory: A Comprehensive Introduction, Academic Press, с. 77–81, ISBN .
Holton, D. A.; Sheehan, J. (1993), The Petersen Graph, Cambridge University Press, с. 183—213, ISBN .
; Phillips, R.; Sarnak, P. (1988), Ramanujan graphs, , 8 (3): 261—277, doi:10.1007/BF02126799, MR 0963118.
Tutte, W. T. (1947), A family of cubical graphs, Proc. Cambridge Philos. Soc., 43 (4): 459—474, doi:10.1017/S0305004100023720.

Посилання

Cages [ 27 грудня 2008 у Wayback Machine.](англ.)
. and (англ.)
Weisstein, Eric W. Cage Graph(англ.) на сайті Wolfram MathWorld.

[1] Bannai, E. and Ito, T. «On Moore Graphs.» J. Fac. Sci. Univ. Tokyo Ser. A 20, 191—208, 1973

[2] Damerell, R. M. «On Moore Graphs.» Proc. Cambridge Philos. Soc. 74, 227—236, 1973

[3] Hoffman, A. J. and Singleton, R. R. «On Moore Graphs of Diameter 2 and 3.» IBM J. Res. Develop. 4, 497—504, 1960