¿Cuál es la interpretación de los valores propios / vectores generalizados en la teoría de grafos espectrales?

Answer 1

Hay todo tipo de cosas que puede decir con respecto a las características espectrales de los gráficos a través de vectores propios, pero casi todos son específicos de los tipos de gráficos. Vea el último teorema a continuación primero, ya que creo que arroja más luz sobre su pregunta. Algunas de las cosas más generales que uno podría decir incluyen:

Teorema Si dos gráficas son y-cospectrales para dos valores distintos de y, entonces son y-cospectrales para todos los valores de y, incluso los valores irracionales de y.

Teorema Sea G muy regular con el conjunto de vértices X de tamaño n, y sea E un valor propio distinto de la valencia k. Sea y = (k – E) / n. Luego, para cada subconjunto S de X, el espectro de G y el espectro y del gráfico inducido en S determina el espectro y del gráfico inducido en X \ S.

Teorema Sea G un gráfico finito y A un grupo de automorfismos. Si H1 y H2 son subgrupos de A, de modo que G es una cobertura de G / Hi (i = 1, 2) y de tal manera que cada clase de conjugación de G cumple con H1 y H2 en el mismo número de elementos, entonces los cocientes G / Hi (i = 1, 2) tienen el mismo espectro y el mismo espectro de Laplace.

Teorema El número de gráficos no DS en n vértices con respecto a la matriz de Laplace es al menos rn (n) ^ (1/2) Gn-1

Teorema Para la matriz de adyacencia, la matriz de Laplace y la matriz de Laplace sin signo de un gráfico G, se puede deducir lo siguiente del espectro:

(a) el número de vértices
(b) el número de aristas
(c) si G es regular
(d) si G es regular con cualquier circunferencia fija

y formar el espectro de la matriz de adyacencia que se obtiene:

(e) el número de caminatas cerradas de cualquier longitud fija
(f) si G es bipartito

y, por último, formar el espectro de la matriz de Laplace:

(g) el número de componentes
(h) el número de árboles de expansión