В математической области теории графов клетка представляет собой правильный граф , имеющий в обхвате как можно меньше вершин .
Формально ( r , g ) -граф определяется как граф , в котором каждая вершина имеет ровно r соседей и в котором кратчайший цикл имеет длину ровно g . ( r , g ) -клетка — это ( r , g ) -граф с наименьшим возможным числом вершин среди всех ( r , g ) -графов . (3, g ) -клетку часто называют g - клеткой .
Известно, что ( r , g ) -граф существует для любой комбинации r ≥ 2 и g ≥ 3 . Отсюда следует, что все ( r , g ) -клетки существуют.
Если граф Мура существует со степенью r и обхватом g , он должен быть клеткой. Более того, границы размеров графов Мура распространяются на клетки: любая клетка нечетного обхвата g должна иметь не менее
вершин, а любая клетка с четным обхватом g должна иметь не менее
вершины. Любой ( r , g ) -граф с ровно таким количеством вершин по определению является графом Мура и, следовательно, автоматически является клеткой.
Для данной комбинации r и g может существовать несколько клеток . Например, существуют три неизоморфные (3, 10) -клетки , каждая из которых имеет 70 вершин: 10-клетка Балабана , граф Харриса и граф Харриса-Вонга . Но есть только одна (3, 11) -клетка : 11-клетка Балабана (со 112 вершинами).
В 1-регулярном графе нет цикла, а связный 2-регулярный граф имеет обхват, равный числу вершин, поэтому клетки представляют интерес только для r ≥ 3. ( r ,3)-клетка представляет собой полный граф K r +1 на r +1 вершинах, а ( r ,4)-клетка представляет собой полный двудольный граф K r , r на 2 r вершинах.
Известные клетки включают:
Число вершин в известных клетках ( r , g ) для значений r > 2 и g > 2, отличных от проективных плоскостей и обобщенных многоугольников, равно:
Для больших значений g граница Мура подразумевает, что число n вершин должно расти по крайней мере однократно экспоненциально в зависимости от g . Эквивалентно, g может быть не более чем пропорциональным логарифму n . Точнее,
Считается, что эта граница является жесткой или близкой к жесткой (Bollobás & Szemeredi 2002). Наиболее известные нижние границы g также являются логарифмическими, но с меньшим постоянным множителем (подразумевается, что n растет экспоненциально, но с более высокой скоростью, чем граница Мура). В частности, конструкция графов Рамануджана, определенная Любоцким, Филлипсом и Сарнаком (1988), удовлетворяет ограничению
Эта граница была немного улучшена Лазебником, Устименко и Вольдаром (1995).
Маловероятно, что эти графы сами являются клетками, но их существование дает верхнюю границу числа вершин, необходимых в клетке.
