Esta pregunta ya tiene una serie de buenas respuestas; quiero destacar la amplitud de este tema.
Los grafos pueden representarse mediante matrices: matrices de adyacencia y varios tipos de matrices laplacianas. matrices laplacianas. Esto plantea casi inmediatamente la cuestión de cuáles son las conexiones entre los espectros de estas matrices y las propiedades de los gráficos. Llamemos al estudio de estas conexiones "teoría de los espectros de grafos". (Pero no estoy del todo satisfecho con esta definición, véase más abajo.) Es tentador ver el mapa de los grafos a los valores propios como una especie de teoría de Fourier, pero hay dificultades con esta analogía. En primer lugar, los gráficos en general no están determinados por sus valores propios. En segundo lugar, ¿cuál de las muchas matrices de adyacencia debemos utilizar?
Los primeros trabajos sobre los espectros gráficos se realizaron en el contexto de la teoría del orbital molecular de Hueckel de Hueckel en la Química Cuántica. Esto llevó, entre otras cosas, a trabajar sobre el polinomio de correspondencia; esto nos da valores propios sin matrices de adyacencia (por lo que considero que la definición anterior del tema es insatisfactoria). Una manifestación más reciente manifestación de esta corriente de ideas es el trabajo sobre los espectros de los fullerenos.
La segunda fuente del tema surge en el trabajo de Seidel sobre los dos grafos regulares, que comenzó con preguntas sobre símiles regulares en el espacio proyectivo real y condujo a cuestiones extraordinariamente interesantes sobre conjuntos de líneas equiangulares en el espacio real. Los análogos complejos de estas cuestiones son ahora de interés para los físicos cuánticos. cuánticos - véase SIC-POVMs. (No está claro qué papel puede desempeñar aquí la teoría de grafos). Paralelamente al trabajo de Seidel, se publicó el artículo fundamental de Hoffman y Singleton sobre los grafos de Moore de diámetro dos. En ambos casos, la observación clave fue que ciertas clases extremas de grafos podían caracterizarse de forma muy natural mediante condiciones sobre sus espectros. Este trabajo cobró impulso porque se construyeron por primera vez una serie de grupos simples esporádicos esporádicos se construyeron por primera vez como grupos de automorfismo de grafos. Para los teóricos de los grafos Para los teóricos de los grafos, se convirtió en la teoría de los grafos regulares a distancia, a partir de el trabajo de Biggs y sus estudiantes, y que sigue siendo muy activo.
Una característica del artículo de Hoffman y Singleton es que su conclusión no hace referencia a los espectros. Así que ofrece un importante resultado teórico de grafos para el que la "prueba de libro" utiliza los valores propios. Muchos de los resultados sobre grafos regulares a distancia conservan esta característica.
Hoffman también es famoso por sus límites de valores propios para los números cromáticos y los límites límites sobre el tamaño máximo de los conjuntos independientes y las camarillas. Esto está estrechamente relacionado con el trabajo de Lovász sobre la capacidad de Shannon. Tanto el teorema de Erdős-Ko-Rado como muchos de sus análogos pueden obtenerse ahora utilizando extensiones de estas técnicas.
Los físicos han propuesto algoritmos para el isomorfismo de grafos basados en los espectros de matrices asociadas a paseos discretos y continuos. Las conexiones entre paseos cuánticos continuos y los espectros de grafos son muy fuertes.
