Si bien la matriz de adyacencia depende del etiquetado del vértice, su espectro es un gráfico invariante, aunque no completo.
La teoría espectral de grafos también abarca con parámetros de grafos definimos por la multiplicidad de los valores propios de aquellas matrices asociadas con el grafo, tales como el número de Colin de Verdière.
Grafos coespectrales
Dos grafos son coespectrales o isoespectrales si sus matrices de adyacencia son, respectivamente, isoespectrales, es decir, que tengan multiconjuntos iguales de valores propios.
Los gráficos coespectrales no son necesariamente isomórficos, pero los gráficos isomórficos son siempre coespectrales.
Grafos determinados por su espectro
Decimos que un grafo está determinado por su espectro si su cualquier otro grafo con el mismo espectro es isomórfico a él.