정도 직경 문제

그래프 이론에서 도 직경 문제는 G에서 정점 중 어떤 것이든 최대 d가 되도록 직경 k의 가능한 가장 큰 그래프 G(정점 집합 V의 크기 측면에서)를 찾는 문제다.G의 크기는 무어 바운드에 의해 위쪽에 경계로 되어 있다; 1 < k >와 2 < d < 피터슨 그래프, 호프만-싱글턴 그래프에 대해서만, 그리고 아마도 직경 k = 2 그리고 도 d = 57의 더 많은 그래프(아직 존재한다는 것이 증명되지 않음)가 무어 바운드에 도달한다.일반적으로 가장 큰 직경 그래프는 무어 바운드보다 크기가 훨씬 작다.

공식

${\displaystyle n_{}}$ d${\displaystyle {,}_{}}$ k ${\$을(를) 최대 d 및 직경 k인 그래프에 대해 가능한 최대 정점 수로 설정하십시오.그런 다음 ${\displaystyle n_{}}$ d${\displaystyle {}_{}}$, ${\displaystyle k_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle M_{}}$ ${\displaystyle {}_{}}$, ${\displaystyle k_{}}$ ${\$ 여기서 ${\displaystyle M_{}}$ d${\displaystyle {}_{}}$, ${\displaystyle k_{}}$ ${\$는 무어 바운드:

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

이 경계는 극소수의 그래프에 대해 달성되므로, 연구는 무어 경계와 얼마나 가까운 그래프로 이동한다.${\displaystyle M_{}}$ d , k${\displaystyle {}_{}}$= ${\displaystyle {}^{}}$ ${\displaystyle k^{}}$+ O${\displaystyle }$(${\displaystyle {\mathrm{d}}^{}}$ k${\displaystyle {}^{}}$- 1${\displaystyle {}^{}}$) ${\dplaystyle M_{d,k}=d^{k}+O(d^{k-1})$라는 점증거동 참고의 경우$.$

매개 $변수{\displaystyle {}_{}}$ ${\displaystyle {\mu k}_{}}$= 림 ${\displaystyle \underset{}{inf}}$d →${\displaystyle \underset{}{\mathrm{}}\frac{{nn}_{}}{}}$ d${\displaystyle \frac{{,}_{}}{}}$ ${\displaystyle \frac{{}_{}}{{}^{}}}$ d ${\displaystyle \frac{k^{}}{}}${\$dplaystyle \mu _{k}=\liminf$ $_$${d_{d}}{d^{k}}}}}{d^{$d$\}\}\}\}\}\}\}$를 정의하십시오. 모든$$ $k$에 $μk$ = 1 ${\displaysty}.$${\displaystyle {\mu 1\mathrm{}}_{}}$= ${\displaystyle {\mu 2\mathrm{}}_{}}$= ${\displaystyle {\mu 3\mathrm{}}_{}}$= μ3 = ${\displaystyle {\mu 5\mathrm{}}_{}}$= ${\displaystyle 1}$ ${\displaystyle \mu _{1}=\mu _{2}=\mu$ _${3$}=\$mu$ ${\displaystyle \_\mathrm{}}$${5}=1$$},$ ${\displaystyle {\mu 4\mathrm{}}_{}\mathrm{\mu 1}}$ /$$4 $displaystystyle \mu \4}\geq$1$/4$

참고 항목

• 케이지(그래프 이론)
• 정도 직경 그래프
• 정점 대칭도 직경 디그래프 표
• 최대 정도 및 직경 경계 서브그래프 문제

참조

• Bannai, E.; Ito, T. (1973), "On Moore graphs", J. Fac. Sci. Univ. Tokyo Ser. A, 20: 191–208, MR 0323615

• Hoffman, Alan J.; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3" (PDF), IBM Journal of Research and Development, 5 (4): 497–504, doi:10.1147/rd.45.0497, MR 0140437

• Singleton, Robert R. (1968), "There is no irregular Moore graph", American Mathematical Monthly, Mathematical Association of America, 75 (1): 42–43, doi:10.2307/2315106, JSTOR 2315106, MR 0225679

• Miller, Mirka; Širáň, Jozef (2005), "Moore graphs and beyond: A survey of the degree/diameter problem", Electronic Journal of Combinatorics, Dynamic survey: DS14

• CombinatoricsWiki - The Degree/Diameter Problem