Qué gráfico Laplacians viaje

Question

Sé que la gráfica Laplaciano de un gráfico completamente conectado desplazamientos con el Laplaciano de cualquier otro gráfico.

¿Hay algún teorema que indica algo similar acerca un poco más general de la familia de los gráficos? Estoy especialmente interesado en saber si hay alguna consecuencia sobre la escasa grafos aleatorios.

Gracias.

--EDIT (Re-instrucción): ¿Qué Laplacians conmuta con un -da - Laplaciano? Una respuesta es la de todos sus poderes y su combinación lineal (ver:Dada una matriz, hay siempre otra matriz que conmuta con ella?) Hay otros gráficos (más general de la familia) con esta propiedad?

Answer 1

Deje $X_{ij}$ el gráfico de $n$ vértices con exactamente uno de los bordes, de unirse a $i$$j$. El Laplaciano de $X_{ij}$$(e_i-e_j)(e_i-e_j)^T$. No es difícil comprobar que si esta desplazamientos con el Laplaciano $L$ de un gráfico de $G$ $v$ es un vértice de $G$ $i$ o $j$, $v$ es adyacente a $i$ si y sólo si es adyacente a $j$.

De ello se sigue que si $L$ viajes con el Laplaciano de $X_{ij}$ todos los $i$$j$, $G$ es un grafo completo, o la gráfica sin bordes.