Проблема диаметра градуса

В теории графов , то проблема диаметра степени является проблемой нахождения наибольшего возможного графа G (в терминах размера его вершина множество V ) от диаметра к такому , что наибольшая степени любым из вершин в G не превосходит г . Размер G ограничен сверху границей Мура ; 1 <  к и 2 <  d только Петерсен граф , то граф Хоффман-Синглтон , и , возможно , еще один график (еще не доказано , что существует) диаметра к = 2 и степень d  = 57 достигают границы Мура. В общем, графы с наибольшим диаметром в градусах намного меньше по размеру, чем граница Мура.

Формула [ править ]

Позвольте быть максимально возможное количество вершин для графа степени не выше d и диаметра k . Тогда , где есть Мур обязан :${\ displaystyle n_ {d, k}}$${\ displaystyle n_ {d, k} \ leq M_ {d, k}}$${\ displaystyle M_ {d, k}}$

${\ displaystyle M_ {d, k} = {\ begin {cases} 1 + d {\ frac {(d-1) ^ {k} -1} {d-2}} & {\ text {if}} d > 2 \\ 2k + 1 & {\ text {if}} d = 2 \ end {case}}}$

Эта оценка достигается для очень небольшого числа графов, поэтому исследование переходит к тому, насколько близки существуют графы к оценке Мура. Обратите внимание, что для асимптотики .${\ Displaystyle M_ {d, k} = d ^ {k} + O (d ^ {k-1})}$

Определите параметр . Предполагается, что для всех k . Известно то и то .${\ displaystyle \ mu _ {k} = \ liminf _ {d \ to \ infty} {\ frac {n_ {d, k}} {d ^ {k}}}}$${\ displaystyle \ mu _ {k} = 1}$${\ Displaystyle \ му _ {1} = \ му _ {2} = \ му _ {3} = \ му _ {5} = 1}$${\ displaystyle \ mu _ {4} \ geq 1/4}$

См. Также [ править ]

• Кейдж (теория графов)
• Таблица графиков градусного диаметра
• Таблица вершинно-симметричных орграфов диаметров степеней
• Задача о подграфе, ограниченном максимальной степенью и диаметром

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

• Bannai, E .; Ито Т. (1973), "О графах Мура", J. Fac. Sci. Univ. Tokyo Ser. А , 20 : 191–208, MR  0323615

• Хоффман, Алан Дж .; Singleton, Роберт Р. (1960), "Мур графы с диаметром 2 и 3" (PDF) , IBM Журнал исследований и разработок , 5 (4): 497-504, DOI : 10,1147 / rd.45.0497 , MR  0140437

• Singleton, Роберт Р. (1968), "Там нет нерегулярного графа Мура", American Mathematical Monthly , Математическая ассоциация Америки, 75 (1): 42-43, DOI : 10,2307 / 2315106 , JSTOR  2315106 , MR  0225679

• Миллер, Мирка ; Ширань, Йозеф (2005), «Графы Мура и не только: обзор проблемы степени / диаметра» , Электронный журнал комбинаторики , Динамический обзор: DS14

• CombinatoricsWiki - проблема степени / диаметра