Por lo general, uno construye un gráfico y luego hace preguntas sobre la descomposición del valor propio de la matriz de adyacencia (o algún pariente cercano como el laplaciano ) (también llamado espectro de un gráfico ).
Pero, ¿qué pasa con el problema inverso? Dados valores propios, ¿puede uno (eficientemente) encontrar un gráfico que tenga este espectro?
Sospecho que, en general, esto es difícil de hacer (y podría ser equivalente a GI), pero ¿qué pasa si relaja un poco las condiciones? ¿Qué pasa si haces condiciones de que no hay multiplicidad de valores propios? ¿Qué pasa con permitir gráficos que tienen espectros de "cierre" por alguna métrica de distancia?
Cualquier referencia o idea sería bienvenida.
EDITAR :
Como señala Suresh, si permite gráficos ponderados no dirigidos con bucles automáticos, este problema se vuelve bastante trivial. Esperaba obtener respuestas en el conjunto de gráficos simples no dirigidos, no ponderados, pero también estaría contento con los gráficos dirigidos simples no ponderados.
Respuestas:
Cvetcovic et todo en la sección 3.3 de "Los resultados recientes en la teoría de los espectros gráfico" va sobre algoritmos para la construcción de gráficos de espectro dado en algunos casos especiales
fuente
Incluso preguntar si existe un gráfico con un espectro dado es una pregunta difícil. Esto es atestiguado por el problema abierto de determinar si existe un gráfico de circunferencia 5 diámetro 2 y orden 3250 cuyo espectro (si existe) es conocido.
fuente
Otro obstáculo para definir su pregunta es que son isospectrales (mismos valores propios) pero gráficos no isomórficos. Entonces, dada una lista de valores propios en tal caso, ¿qué gráfico quieres? ¿Quizás solo desee que un algoritmo devuelva un elemento aleatorio del conjunto de gráficos no isomórficos?
fuente