Diámetro de un gráfico de Johnson

Question

Estoy leyendo el libro Algebraic Graph Theory, de Godsil y Royle, y actualmente estoy haciendo los ejercicios del primer capítulo. En uno de ellos me encargan determinar el diámetro de un grafo de Johnson con $v > 2k$ .

En el primer capítulo del libro no profundizan mucho en los gráficos de Johnson, aparte de dar la definición. No sé cómo enfocar esto. He leído en wikipedia que los gráficos de Johnson son $k(n-k)$ -regular, y conozco el número de vértices, ¿podría utilizarse para calcular el diámetro? Y en caso afirmativo, ¿cómo podría demostrar su regularidad para luego calcular el diámetro?

Answer 1

El gráfico Johnson $J(v,k)$ se define del siguiente modo. Los vértices de $J(v,k)$ son los $k$ -subconjuntos de elementos de un $v$ -conjunto de elementos $X$ . Dos vértices $V,W\subset X$ son adyacentes cuando $|V\cap W|=k-1$ .

Proposición. Si $v>2k$ entonces $\operatorname{diam}(J(v,k))=k$ .

Prueba . Sea $V=\{v_1,\ldots,v_k\}\subset X,W=\{w_1,\ldots,w_k\}\subset X$ se elija de forma que $V\cap W=\varnothing$ . Sea $V_i=\{w_1,\ldots,w_i,v_{i+1},\ldots,v_k\}$ , $i=0,1,\ldots,k$ . Tenemos $V_0=V$ , $V_k=W$ y $V_i\cap V_{i+1}=\{w_1,\ldots,w_i,v_{i+2},\ldots,v_k\}$ . Por lo tanto, los vértices $V_i$ y $V_{i+1}$ son adyacentes para $i=0,1,\ldots,k-1$ . Esto significa que la distancia entre $V$ y $W$ es como máximo $k$ .

Demostremos ahora que la distancia entre $V$ y $W$ no puede ser inferior a $k$ . Sea $U_0=V,U_1,\ldots,U_s=W$ sea un camino entre $V$ y $W$ de longitud $s<k$ . Entonces $$ |U_0\cup U_1|= k+1, |U_0\cup U_1\cup U_2|\leq k+2, \dots, |U_0\cup U_1\cup\ldots\cup U_s|\leq k+s<2k. $$ Obtenemos una contradicción ya que $V\cup W\subset U_0\cup U_1\cup\ldots\cup U_s$ y $|V\cup W|=2k$ .