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

Тутта (3,8) -cage .

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

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

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

${\ Displaystyle 1 + г \ сумма _ {я = 0} ^ {(г-3) / 2} (г-1) ^ {я}}$

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

${\ Displaystyle 2 \ сумма _ {я = 0} ^ {(г-2) / 2} (г-1) ^ {я}}$

вершины. Любой ( r , g ) -граф с таким количеством вершин по определению является графом Мура и, следовательно, автоматически клеткой.

Для данной комбинации r и g может существовать несколько клеток . Например , существует три неизоморфные (3,10) -cages, каждые с 70 вершинами: при регистрации Балабан 10-клетки , то граф Харриес и граф Харриес-Вонг . Но есть только одна (3,11) -клетка: 11-клетка Балабан (со 112 вершинами).

Известные клетки [ править ]

Граф первой степени не имеет цикла, а связный граф второй степени имеет обхват, равный количеству вершин, поэтому клетки представляют интерес только при r ≥ 3. ( r , 3) -клетка - это полный граф K _{r +1} на r +1 вершинах, а ( r , 4) -клетка - это полный двудольный граф K _{r , r} на 2 r вершинах.

Другие известные клетки включают:

• (3,5) -клетка: граф Петерсена , 10 вершин
• (3,6) -клетка: граф Хивуда , 14 вершин
• (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, кроме проективных плоскостей и обобщенных многоугольников, составляет:

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

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

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

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

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

Эта оценка была немного улучшена Lazebnik, Ustimenko & Woldar (1995) .

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

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

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

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

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