Problém s průměrem stupně - Degree diameter problem

v teorie grafů, problém s průměrem stupně je problém najít co největší možnou graf G (z hlediska velikosti jeho vrchol soubor PROTI) z průměr k takové, že největší stupeň kteréhokoli z vrcholů v G je nanejvýš d. Velikost G je výše ohraničen Moore vázán; pro 1 <k a 2 <d pouze Petersenův graf, Hoffman-Singletonův graf a případně ještě jeden graf (dosud neprokázaný) průměru k = 2 a stupeň d = 57 dosáhne Moorovy hranice. Obecně platí, že grafy s největším průměrem mají mnohem menší velikost, než je tomu u Moora.

Vzorec

Nechat ${displaystyle n_ {d, k}}$ být maximální možný počet vrcholů pro graf s maximálním stupněm d a průměr k. Pak ${displaystyle n_ {d, k} leq M_ {d, k}}$, kde ${displaystyle M_ {d, k}}$ je Moore vázán:

${displaystyle M_ {d, k} = {egin {cases} 1 + d {frac {(d-1) ^ {k} -1} {d-2}} & {ext {if}} d> 2 2k + 1 & {ext {if}} d = 2end {cases}}}$

Této hranice je dosaženo u velmi málo grafů, takže se studie posouvá k tomu, jak blízko existují grafy k Mooreově vazbě. U asymptotického chování si povšimněte, že ${displaystyle M_ {d, k} = d ^ {k} + O (d ^ {k-1})}$.

Definujte parametr ${displaystyle mu _ {k} = liminf _ {d o infty} {frac {n_ {d, k}} {d ^ {k}}}}$. Předpokládá se to ${displaystyle mu _ {k} = 1}$ pro všechny k. Je známo že ${displaystyle mu _ {1} = mu _ {2} = mu _ {3} = mu _ {5} = 1}$ a to ${displaystyle mu _ {4} geq 1/4}$.

Viz také

• Cage (teorie grafů)
• Tabulka grafů průměrů stupňů
• Tabulka digrafů o průměru vrcholů a symetrických stupňů
• Problém podgrafu ohraničeného maximálním stupněm a průměrem

Reference

• Bannai, E .; Ito, T. (1973), „On Moore graphs“, J. Fac. Sci. Univ. Tokio Ser. A, 20: 191–208, PAN  0323615

• Hoffman, Alan J.; Singleton, Robert R. (1960), „Mooreovy grafy o průměru 2 a 3“ (PDF), IBM Journal of Research and Development, 5 (4): 497–504, doi:10.1147 / kolo 45.0497, PAN  0140437

• Singleton, Robert R. (1968), „Neexistuje nepravidelný Mooreův graf“, Americký matematický měsíčník, Mathematical Association of America, 75 (1): 42–43, doi:10.2307/2315106, JSTOR  2315106, PAN  0225679

• Miller, Mirka; Širáň, Jozef (2005), „Mooreovy grafy a další: Přehled problému stupňů / průměrů“, Electronic Journal of Combinatorics, Dynamický průzkum: DS14

• CombinatoricsWiki - Problém stupně / průměru