n-клетка — кубический граф обхвата n с наименьшим возможным числом вершин. Граф называется кубическим, если из каждой его вершины выходят 3 ребра. Обхват графа — это длина наименьшего цикла в нём.
Для каждого 2 < n < 9 существует единственная n-клетка, причем все эти графы обладают высокой симметрией (являются унитранзитивными). Кроме того, при изображении на плоскости они часто дают экстремальное количество самопересечений, далее Шаблон:Нп1.
4-клетка — К3,3, один из двух минимальных не планарных графов, 6 вершин.
5-клетка — Граф Петерсена, 10 вершин. Минимальный кубический граф с индексом самопересечения 2.
6-клетка — Граф Хивуда, 14 вершин. Разбивается на 1-факторы (то есть, реберно раскрашиваем), любая сумма двух факторов образует гамильтонов цикл. Минимальный кубический граф с индексом самопересечения 3.
7-клетка — Граф МакГи, 24 вершины. Минимальный кубический граф с индексом самопересечения 8.
Известны ещё некоторые клетки. В таблице ниже показано количество вершин в (r,n)-клетках степени 3≤r≤7 и обхвата 3≤n≤12. Клетки для этих и бо́льших r и n описаны здесь: [1] (на английском языке).
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)-клетке больше или равно
<math>1+r\sum_{i=0}^{(n-3)/2}(r-1)^i</math> для нечётных n и
<math>2\sum_{i=0}^{(n-2)/2}(r-1)^i</math> для чётных.
Если имеет место равенство, то соответствующий граф называется графом Мура. В то время как клетка существует для всяких r > 2 и n > 2, нетривиальных графов Мура гораздо меньше. Из вышеупомянутых клеток, графами Мура являются Граф Петерсена, граф Хивуда, граф Татта — Коксетера и граф Хоффмана — Синглтона. Доказано,[1][2][3] что все нечётные случаи исчерпываются n = 5, r = 2, 3, 7 и, возможно, 57, а чётные n = 6, 8, 12.
