Diameter of complement with diameter condition (complement of graph) / Graph Theory Prob. #3

문제

Let G be a simple graph with diameter at least 4. Prove that \overline{G} has diameter at most 2.

Complement of Graph

n-vertex graph G의 complement \overline{G}는 다음과 같이 정의된다.

  • V(G)=V(\overline{G})
  • E(G)\cup E(\overline{G})=E(K_{n})
  • E(G)\cap E(\overline{G})=\phi

G\overline{G}는 vertices를 공유하며 edges는 하나도 겹치지 않는 동시에, 합치면 complete graph가 되는 관계이다.

풀이

\text{diam}(G)=k\geq 4라고 하자. d_G(v_0,v_k)=kv_0,v_k\in V(G)가 존재한다는 의미이다. d_G(v_0,v_k)=k를 만족시키는 v_0v_k-path를 다음과 같이 정의하자.

v_0~v_1~v_2\cdots v_{k-1} v_k

이 때, d_{\overline{G}}(v_i,v_j)|i-j|=1이면 2이고, |i-j|\neq 1이면 1이다. 이외의 vertex xv_i의 관계를 살펴보자.

  1. x가 모든 v_i~(i=0,\cdots,k)와 adjacent하지 않는 경우, d_G(x,v_0)d_G(x,v_k)가 모두 k보다 작거나 같아야 한다. 이 경우, d_{\overline{G}}(x,v_i)=1~(i=1,\cdots,k)이 된다.
  2. xv_i와 adjacent한 경우, v_0또는 v_k와는 adjacent할 수 없다. xv_n에 adjacent한다면 v_{n+2} 또는 v_{n-2}와만 추가적으로 adjacent할 수 있다. 만약 v_{n+1} 또는 v_{n-1}에 adjacent하다면 \text{diam}(G)=k+1이 되며 다른 v_i와 adjacent하면 \text{diam}(G)k보다 작아진다.
    xG 상에서 v_n과 adjacent한 경우, 나머지 v_i와는 d_{\overline{G}}(x,v_i)=1이 되며, d_{\overline{G}}(x,v_n)=2가 된다.
    비슷하게, xG 상에서 v_nv_{n+2}와 adjacent인 경우, 나머지 v_i와는 d_{\overline{G}}(x,v_i)=1이 되며, d_{\overline{G}}(x,v_n)=d_{\overline{G}}(x,v_{n+2})=2가 된다.

이제 path 외의 vertices xy의 관계를 살펴보자. 만약 xyG 상에서 adjacent하지 않다면, d_{\overline{G}}(x,y)=1이므로 문제가 되지 않는다. xyG 상에서 adjacent하다면, \overline{G} 상에서는 adjacent하지 않으므로 xy의 상태에 따라서 경우를 나누어 생각해보자.

  • xy가 모두 1번인 경우
    xy 사이에 어떤 v_i를 거쳐서 이어질 수 있으므로 d_{\overline{G}}(x,y)=2가 된다.
  • x는 1번 y는 2번인 경우
    d_{\overline{G}}(y,v_i)=1v_i에 대해서 d_{\overline{G}}(x,v_i)=1이므로 d_{\overline{G}}(x,y)=2가 된다.
  • xy가 모두 2번인 경우
    최악의 경우의 수를 생각해보자. k=4여서 path의 길이가 가장 짧은 상황을 가정하자. (v_0~v_1~v_2~v_3~v_4, 5개의 vertices) xv_0v_2와 adjacent하고 yv_1v_3와 adjacent하다고 하더라도 d_{\overline{G}}(x,v_4)=1이고, d_{\overline{G}}(y,v_4)=1이므로 d_{\overline{G}}(x,y)=2가 된다.

결과적으로, 임의의 vertices u, v에 대해서 d_{\overline{G}}(u,v)\leq 2가 되므로 \text{diam}(\overline{G})\leq 2가 된다.

Leave a Comment

Index