graph의 order 범위에 관한 문제

1. 상한

graph \(G\)의 radius \(k\), maximum degree \(d = \Delta (G) \)에 대해 다음이 성립한다.

\[|G| \le 1 + d \sum _{i=0} ^{k-1} (d-1)^i \]

증명

\(z\)를 \(G\)의 central vertex로 놓자.

\[D_i := \{v|v\in V \wedge d(v,z) = i\}\]

점 집합 \(D_i\)를 \(z\)로부터의 거리가 \(i\)인 점들의 집합으로 놓자. 그러면 다음이 성립한다.

\[V(G) = \bigcup _{i=0} ^k D_i \]

정의에 의해 \(D_i \cap D_j = \emptyset \)이므로 \(|G| = \sum _{i=0} ^k |D_i|\)이다.

여기서 귀납적으로 접근하면

\(|D_0| = 1\)(central vertex), \(|D_1| \le d\), \(|D_2| \le d(d-1)\)(central vertex와 \(D_1\)사이의 edge를 제외하므로), \(|D_2| \le d(d-1)^2 \), \(\cdots\), \(|D_n| \le d(d-1)^{n-1} \)이다.

결론적으로

\[|G| = \sum _{i=0} ^k |D_i| = |D_0| + \sum_{i=1} ^k |D_i| = 1 + d\sum_{i=0} ^{k-1} (d-1)^i \]

등비급수를 정리해서 식을 더 간단하게 나타낼 수도 있지만 생략한다.

2. 하한

graph \(G\)의 minimum degree \(\delta\), girth \(g\)에 대해 다음이 성립한다.

\[ n_0(\delta, g) := \left\{\begin{matrix} 1 + \delta \sum\limits _{i=0} ^{r-1} (\delta-1)^i \quad \text{if} \; g:=2r+1 \; \text{is odd}\\ 2\sum\limits _{i=0} ^{r-1} (\delta-1)^i \qquad \quad \text{if} \; g:=2r \; \text{is even} \quad \,  \end{matrix}\right. \quad \text{then} \; n_0( \delta,g) \le |G| \]

\(g\)가 짝수라면

girth가 계산된 cycle에서 이웃한 두 점을 \(x,y\)로 잡자. 여기서 각 점에 대해 다음 집합을 정의한다.

\[ X_i := \{v|v\in V \wedge d(x,v)=i \}\]

\[ Y_i := \{v|v \in V \wedge d(y,v)=i\}\]

이 집합을 정의할 때 edge \(xy\)는 없다고 보고 정의한다.

이 때 \( V(G) \ge \bigcup _{i=0} ^{r-1} X_i \cup Y_i \), \((X_i \cup Y_i) \cap (X_j \cup Y_j )=\emptyset \), \(X_i \cap Y_i = \emptyset \) 이므로, (그 이유는 girth의 정의에 모순되지 않은 cycle만 그려져야 하기 때문)

\[|G| \ge \sum _{i=0} ^{r-1} |X_i| +|Y_i| \]

대칭성에 의해 정리하면 다음과 같다.

\[|G| \ge 2 \sum _{i=0} ^{r-1} (\delta - 1)^2 \]

\(g\)가 홀수라면

girth가 계산된 cycle에서 한 점 \(z\)를 잡자. \(Z_i := \{v|v \in V \wedge d(x,v) = i \}\)라는 점집합들을 정의했을 때 \(V(G) \ge \bigcup _{i=0} ^r Z_i \)이다. \(V_i \cap V_j = \emptyset\)이므로 상한 문제와 같이 귀납적으로 \(|G|\)를 접근하면 다음과 같은 결론이 나온다.

\[|G| \ge \sum _{i=0} ^{r} |V_i| = 1 + d \sum _{i=0} ^{r-1} (d-1)^i \]

\(\square\)