¿Cómo puedo demostrar que el índice de Wiener del gráfico del hipercubo es $k \cdot 4^{k-1}$ ?

Question

Estoy tratando de encontrar el índice de Wiener del gráfico del hipercubo, $Q_k$ . Por si alguien no sabe lo que es, se trata de un gráfico en el que cada vértice está etiquetado por un binario $k$ -y donde dos vértices se conectan sólo si las tuplas difieren en un solo lugar. Así, por ejemplo, $Q_2$ tendría vértices etiquetados $(0, 0), (0, 1), (1, 0)$ y $(1, 1)$ . $(0, 0)$ se conectaría a $(0, 1)$ y $(1, 0)$ y así sucesivamente.

Escribí algunos ejemplos y creo que el índice de Wiener del gráfico se puede representar por $k \cdot 4^{k-1}$ . Pero, ¿cómo puedo demostrarlo? La única idea que se me ocurre es utilizar la inducción, pero no estoy del todo seguro de cómo hacerlo. Se agradecería cualquier ayuda al respecto. Si alguien tiene alguna otra idea para una prueba, también estaría bien.

Answer 1

Considere el vértice $\mathbf 0=(0,0,\dots,0)$ del gráfico del hipercubo $Q_n$ . Para cada $r\in[n]=\{1,2,\dots,n\}$ hay $\binom nr$ vértices a una distancia de $r$ de $\mathbf 0$ Así que $$\sum_{v\in V(Q_n)}\operatorname{d}(\mathbf 0,v)=\sum_{r=1}^nr\binom nr.$$ Dado que todos los vértices de $Q_n$ son similares, el Índice de Wiener de $Q_n$ es igual a $$\frac12\sum_{u\in V(Q_n)}\sum_{v\in V(Q_n)}\operatorname{d}(u,v)=\frac12\cdot2^n\sum_{r=1}^n r\binom nr=2^{n-1}\sum_{r=1}^n r\binom nr.$$ Diferenciación de la identidad binomial $$\sum_{r=0}^n\binom nrx^r=(1+x)^n$$ obtenemos $$\sum_{r=1}^n r\binom nrx^{r-1}=n(1+x)^{n-1};$$ en la configuración $x=1$ tenemos $$\sum_{r=1}^n r\binom nr=n2^{n-1},$$ por lo que el índice de Wiener de $Q_n$ es igual a $$2^{n-1}\sum_{r=1}^n r\binom nr=2^{n-1}\cdot n2^{n-1}=n4^{n-1}.$$

Answer 2

Para dos gráficos cualesquiera $G$ y $H$ tenemos $$ W(G \square H ) = |V(G)|^2 W(H) + |V(H)|^2W(G),$$ donde $W(G)$ es el índice de Wiener de $G.$

Ahora el gráfico del hipercubo $Q_k = Q_{k-1} \square K_2$ y el resultado ahora se sigue inmediatamente por inducción.