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

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

Формула

Пусть ${\displaystyle n_{d,k}}$ — максимально возможное число вершин графа со степенью, не превосходящей ${\displaystyle d}$ , и диаметром ${\displaystyle 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}}&d\geqslant 2\\2k+1&d=2\end{cases}}}$

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

Величина ${\displaystyle \delta =M_{d,k}-|V|}$ называется дефектом графа (здесь ${\displaystyle |V|}$ — число вершин в графе). Говорят, что граф имеет малый дефект , если ${\displaystyle \delta \leqslant d}$ . Есть гипотеза, что для степеней ${\displaystyle d\geqslant 6}$ не существует ${\displaystyle (d,2)}$ -графов с дефектом 2. О графах с дефектом, большим 2, известно мало .

Для асимптотического поведения заметим, что ${\displaystyle M_{d,k}=d^{k}+O(d^{k-1})}$ .

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

MaxDDBS

Если дан связный граф-хозяин ^{[ уточнить ]} ${\displaystyle G}$ , верхняя граница степени ${\displaystyle d}$ и верхняя граница диаметра ${\displaystyle k}$ , ищется наибольший подграф ${\displaystyle S}$ графа ${\displaystyle G}$ с максимальной степенью, не превосходящей ${\displaystyle d}$ и диаметром, не превосходящим ${\displaystyle k}$ . Эта задача называется MaxDDBS, и она содержит проблему размера — диаметра в качестве частного случая (а именно, если взять достаточно большой полный граф в качестве графа-хозяина). Задача является NP-трудной .

Примечания

Литература

• Молодцов С. Г. // Дискретный анализ и исследование операций : Тезисы докладов. — Новосибирск, Академгородок: Институт математики им. С.Л. Соболева СО РАН, 2004. — Вып. 28 июня - 2 июля 2004 . — С. 109 .
• Bannai E., Ito T. On Moore graphs // J. Fac. Sci. Univ. Tokyo Ser. A. — 1973. — Т. 20 . — С. 191–208 .
• Hoffman Alan J., Singleton Robert R. // IBM Journal of Research and Development. — 1960. — Т. 5 , вып. 4 . — С. 497–504 . — doi : .
• Singleton Robert R. // American Mathematical Monthly . — 1968. — Т. 75 , вып. 1 . — С. 42–43 . — doi : . — JSTOR .
• Miller Mirka, Širáň Jozef. // . — 2005. — Т. Dynamic survey . — С. DS14 .
• (неопр.) .
• Miller Mirka. // Extended abstracts of IWONT. — Barcelona, 2010, 2010. — С. 335—346 .
• Dekker A., Perez-Roses H., Pineda-Villavicencio G., Watters P. The Maximum Degree & Diameter-Bounded Subgraph and its Applications // Journal of Mathematical Modelling and Algorithms. — 2012. — doi : .
• Miller M., Perez-Roses H., Ryan J. The Maximum Degree and Diameter Bounded Subgraph in the Mesh. Discrete Applied Mathematics. — 2012. — doi : .