Es este gráfico y su espectro se entiende?

Question

Considere el grafo cuyos vértices son etiquetados por la representación binaria de los números enteros de $0$ a $2^{d}-1$ para algunos $d \in \mathbb{N}$. Así que es un gráfico con $2^d$ vértices. Una ventaja que existe entre dos vértices si las dos cadenas binarias difieren en más de 2 bits. (por ejemplo, para $d=2$ esto es $K_4$. para $d=3$ este es el cubo con toda la faz de las diagonales)

Es este gráfico y su espectro conocido? Si algo es conocido acerca de este gráfico del espectro, a continuación, latas de alguien por favor dar las referencias?

Answer 1

Este gráfico se conoce generalmente como la mitad $n$-cubo. Se discute en la página 264 de Brouwer, Cohen y Neumaier "a Distancia Regular de Gráficos". A partir de ahí vemos que los valores propios son \[ \theta_j = \frac12(n-2j)^2-\frac12n \] con sus respectivas multiplicidades $\binom{n}{j}$ al $2j<n$; si $n=2d$ entonces $\theta_d$ tiene multiplicidad $\frac12\binom{n}{d}$.

Voy a describir una forma de obtener los autovalores. Deje $A_1$ denotar la matriz de adyacencia de la $n$-cubo y deje $A_2$ ser la matriz de adyacencia del grafo con los mismos vértices como el $n$-cubo, pero con dos vértices adyacentes si y sólo si están a una distancia de dos en el $n$-cubo. (Esta gráfica tiene dos componentes, cada uno de los cuales es una mitad, $n$- cubo.) Entonces tenemos \[ A_1^2 = nI+2A_2 \] y, por tanto,$A_2=\frac12(A_1^2-nI)$. Los autovalores de la $n$-cubo son los enteros $n-2r$ para $r=0,\ldots,n$, con lo que obtenemos los valores propios de la mitad $n$-cube s arriba.