¿Cuál es la multiplicidad del mayor valor propio de un gráfico?

Hay gráficos en$n^2$vértices con mayor valor propio laplaciano de multiplicidad$n^2-3n+2$.

Estos gráficos son los llamados gráficos cuadrados latinos. Para obtener detalles sobre su construcción, consulte, por ejemplo, http://www.cs.yale.edu/homes/spielman/561/2009/lect23-09.pdf . El resumen es que desde un$n\times n$Cuadrado latino obtenemos un gráfico en$n^2$vértices regulares de grado$3n-3$. El valor propio mínimo de su matriz de adyacencia es$-3$con multiplicidad$n^2-3n+2$; se convierte en un valor propio$3n$del Laplaciano, y este es el más grande.