Кейдж (теория графов)

В математической области теории графов клетка правильный представляет собой граф меньше вершин как можно , имеющий в обхвате .

Формально $(r, g)$ -граф определяется как граф , в котором каждая вершина имеет ровно $r$ соседей и в котором кратчайший цикл имеет длину ровно $g$ . -клетка $(r, g)$ — это $(r, g)$ -граф с наименьшим возможным числом вершин среди всех $(r, g)$ -графов . -клетку $(3, g)$ - часто называют $g$ клеткой .

Известно, что $(r, g)$ -граф существует для любой комбинации $r \geq 2$ и $g \geq 3$ . Отсюда следует, что все $(r, g)$ -клетки существуют.

Если граф Мура существует со степенью $r$ и обхватом $g$ , он должен быть клеткой. Более того, границы размеров графов Мура распространяются на клетки: любая клетка нечетного обхвата $g$ должна иметь не менее

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

вершин, а любая клетка с четным обхватом $g$ должна иметь не менее

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

вершины. Любой $(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 вершинах.

Известные клетки включают:

(3,5)-клетка: граф Петерсена , 10 вершин
(3,6)-клетка: граф Хивуда , 14 вершин
(3,7)-клетка: граф МакГи , 24 вершины
(3,8)-клетка: граф Тутта–Коксетера , 30 вершин
(3,10)-клетка: Балабан 10-клетка , 70 вершин
(3,11)-клетка: 11-клетка Балабана , 112 вершин
(4,5)-клетка: граф Робертсона , 19 вершин
(7,5)-клетка: граф Хоффмана–Синглтона , 50 вершин.
Когда r − 1 — степень простого числа, клетки ( r ,6) — это графы инцидентности проективных плоскостей .
Когда r − 1 является степенью простого числа, клетки ( r ,8) и ( r ,12) представляют собой обобщенные многоугольники .

Число вершин в известных клетках ( r , g ) для значений r > 2 и g > 2, отличных от проективных плоскостей и обобщенных многоугольников, равно:

г р	3	4	5	6	7	8	9	10	11	12
3	4	6	10	14	24	30	58	70	112	126
4	5	8	19	26	67	80				728
5	6	10	30	42		170				2730
6	7	12	40	62		312				7812
7	8	14	50	90

Асимптотика [ править ]

Для больших значений g граница Мура подразумевает, что число n вершин должно расти по крайней мере однократно экспоненциально в зависимости от g . Эквивалентно, g может быть не более чем логарифму n пропорциональным . Точнее,

g\leq 2\log _{r-1}n+O(1).

Считается, что эта граница является жесткой или близкой к жесткой ( Bollobás & Szemerédi 2002 ). Наиболее известные нижние границы g также являются логарифмическими, но с меньшим постоянным множителем (подразумевается, что n растет экспоненциально, но с более высокой скоростью, чем граница Мура). В частности, конструкция графов Рамануджана, определенная Любоцким, Филлипсом и Сарнаком (1988), удовлетворяет ограничению

g\geq {\frac {4}{3}}\log _{r-1}n+O(1).

Эта граница была немного улучшена Лазебником, Устименко и Вольдаром (1995) .

Маловероятно, что эти графы сами являются клетками, но их существование дает верхнюю границу числа вершин, необходимых в клетке.

Ссылки [ править ]

Биггс, Норман (1993), Алгебраическая теория графов (2-е изд.), Кембриджская математическая библиотека, стр. 180–190, ISBN 0-521-45897-8 .
Боллобас, Бела ; Семереди, Эндре (2002), «Обхват разреженных графов», Journal of Graph Theory , 39 (3): 194–200, doi : 10.1002/jgt.10023 , MR 1883596 .
Эксу, Дж; Джайкай, Р. (2008), «Динамическое исследование клетки» , Dynamic Surveys, Electronic Journal of Combinatorics , DS16 , заархивировано из оригинала 1 января 2015 г. , получено 25 марта 2012 г.
Эрдос, Пол ; Реньи, Альфред ; Сос, Вера Т. (1966), «Об одной задаче теории графов» (PDF) , Studia Sci. Венгерский. , 1 : 215–235, заархивировано из оригинала (PDF) 9 марта 2016 г. , получено 23 февраля 2010 г.
Хартсфилд, Нора ; Рингель, Герхард (1990), Жемчужины теории графов: всестороннее введение , Academic Press, стр. 77–81 , ISBN 0-12-328552-6 .
Холтон, Д.А.; Шихан, Дж. (1993), График Петерсена , Cambridge University Press , стр. 183–213, ISBN 0-521-43594-3 .
Лазебник Ф.; Устименко В.А.; Волдар, AJ (1995), «Новая серия плотных графов большого обхвата», Бюллетень Американского математического общества , New Series, 32 (1): 73–79, arXiv : math/9501231 , doi : 10.1090/S0273- 0979-1995-00569-0 , МР 1284775 .
Любоцкий, А. ; Филлипс, Р.; Сарнак, П. (1988), «Графы Рамануджана», Combinatorica , 8 (3): 261–277, doi : 10.1007/BF02126799 , MR 0963118 .
Тутте, В.Т. (1947), "Семейство кубических графов", Proc. Кембриджская философия. Соц. , 43 (4): 459–474, Бибкод : 1947PCPS...43..459T , doi : 10.1017/S0305004100023720 .

Внешние ссылки [ править ]

Брауэр, Андрис Э. Кейджс
Ройл, Гордон. Кубические клетки и клетки высшей валентности
Вайсштейн, Эрик В. «Клеточный граф» . Математический мир .