Dos gráficos$G_1$ y$G_2$ que son cospectrales (multicentros de autovalores de sus matrices de adyacencia son los mismos), no tienen que ser isomorfos. El par de gráficos cospectrales que sirven como el contraejemplo más pequeño para el isomorfismo son la unión gráfica disjunta de$C_4 \cup K_1$ y el gráfico de estrellas$S_5$.
¿Cuál es el contraejemplo más pequeño que se conoce cuando requerimos que$G_1$ y$G_2$ estén conectados?
Harary, King, Mowshowitz, Read, gráficos y dígrafos cospectrales, Bull London Math Soc 3 (1971) 321-328, dan un ejemplo de dos gráficos conectados, cospectrales, no isomórficos en 6 vértices, y afirman, sobre la base de una búsqueda exhaustiva, que es el más pequeño.
EDITAR: Aquí está el ejemplo. Deje que los vértices sean$A,B,C,D,E,F$. Para un gráfico, une$A$ a cada uno de los otros vértices, luego únete a$BC$ y$DE$. Para el otro, dibuja un camino$ABCDE$, luego únete a$F$ a$B,C,D$.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
