В математической области теории графов клетка — это регулярный граф , имеющий минимально возможное количество вершин для своего обхвата .
Формально ( 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 & Szemerédi 2002). Наиболее известные нижние границы для g также являются логарифмическими, но с меньшим постоянным множителем (подразумевая, что n растет экспоненциально, но с большей скоростью, чем граница Мура). В частности, конструкция графов Рамануджана, определенная Любоцки, Филлипсом и Сарнаком (1988), удовлетворяет границе
Эта граница была немного улучшена Лазебником, Устименко и Вольдаром (1995).
Маловероятно, что эти графы сами по себе являются клетками, но их существование дает верхнюю границу количества вершин, необходимых в клетке.
