Distancia media del gráfico totalmente conectado con cola

Question

Tengo un grafo que está totalmente conectado con $n$ y tiene una cola de longitud $c$ adjunto:

En este ejemplo, n = 4 y c = 3.

En general, el diámetro de este gráfico es $1+c$ (atravesar desde el final de la cola hasta uno de los nodos del componente totalmente conectado).

¿Es posible encontrar una expresión para la distancia media (=distancia media entre todos los pares de nodos del grafo) de este grafo?

Answer 1

Sea $K_n$ sea su parte totalmente conexa con conjunto de vértices $v_1,\ldots,v_n$ . Sea $P=(w_c,w_{c-1},\ldots,w_1)$ sea tu cola donde $w_1$ está conectado a $v_1$ por una sola arista.

Denote la distancia entre vértices $a$ y $b$ por $d(a,b)$ .

Caso 1 : $a=v_i$ y $b=v_j$ para algunos $i\neq j$ . Entonces $d(v_i,v_j)=1$ así que $$\sum_{i,j,i\neq j} d(v_i,v_j) =\sum_{i,j,i\neq j} 1 ={n\choose 2}.$$

Caso 2 : $a=w_i$ y $b=v_1$ : Entonces $d(a,b)=i$ así que $$\sum_{i=1}^c d(w_i,v_1) = 1+2+\cdots c = {c+1\choose 2}.$$

Caso 3 : $a=w_i$ y $b=v_j$ para $j\neq 1$ . Entonces $d(a,b)=i+1$ . Así $$\sum_{j=2}^n\sum_{i=1}^c d(w_i,v_j) = \sum_{j=2}^n\sum_{i=1}^c i+1 = (n-1)\left({c+1\choose 2}+c\right).$$

Caso 4 : $a=w_i$ y $b=w_j$ para algunos $i<j$ . Entonces $d(a,b)=j-i$ . Así que $$\sum_{j=1}^c\sum_{i=1}^{j-1} d(w_j,w_i) = \sum_{j=1}^c\sum_{i=1}^{j-1} j-i = {c+1\choose 3}.$$

Si lo juntamos todo, vemos que la distancia media es de

$$\frac{{n\choose 2}+n{c+1\choose 2}+c(n-1)+{c+1\choose 3}}{{n+c\choose 2}}.$$