Sesión Matemática DiscretaGrafos circulantes singularmente coespectrales
Ezequiel Dratman
Universidad Nacional de General Sarmiento, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Un grafo $G=G(\mathbb{Z}_n,S)$ es circulante de orden $n$ si los vértices de $G$ son los elementos de $\mathbb{Z}_n$, e $ij$ es una arista de $G$ si y solo si $j-i\in S$, donde $S$ es un subconjunto de $\mathbb{Z}_n\setminus\{0\}$ cerrado con respecto a tomar inverso aditivo, es decir, $S=-S$. Es fácil de ver que la matriz de adyacencia $A_G$, para este tipo de grafos, es una matriz circulante para cierto orden de sus vértices. Los grafos circulantes han sido muy estudiados (ver [1] y las referencias presentes en él). En conexión con el espectro de los grafos circulantes, en 2006, So caracterizó aquellos que tienen autovalores enteros [2] y conjeturó que los grafos circulantes integrales son isomorfos si y solo si son coespectrales. Sander y Sander probaron esta conjetura en 2015 [3].
Recientemente, Conde, Dratman y Grippo presentaron condiciones necesarias y suficientes para que dos grafos sean singularmente coespectrales [4] (es decir los valores absolutos de sus autovalores no nulos coinciden). En el mismo artículo, presentan familias de parejas de grafos singularmente coespectrales no isomorfos y clases de grafos donde coespectralidad singular implica casi coespectralidad, es decir, que los autovalores no negativos coinciden, contados con multiplicidad.
La energía de un grafo fue definida por Gutman en 1978 como la suma de sus valores singulares contados con multiplicidad [5]. En 2005, Stevanović y Stanković probaron que casi todos los grafos circulantes son hiperenergéticos [6], es decir, sus energías son mayores que dos veces el número de vértices menos uno. Blackburn y Shparlinski, en 2008, encuentran cotas superiores e inferiores para la energía promedio de los grafos circulantes [7].
En esta comunicación, nos enfocamos en la búsqueda de familias de parejas de grafos circulantes no coespectrales singularmente coespectrales, con una cantidad de vértices par. Para una cantidad prima impar de vértices, probamos que no hay parejas de grafos circulantes singularmente coespectrales no isomorfos.
Trabajo en conjunto con: Cristian M. Conde (Universidad Nacional de General Sarmiento), Luciano N. Grippo (Universidad Nacional de General Sarmiento) y Melina Privitelli (Universidad Nacional de General Sarmiento).
Referencias
[1] E. A. Monakhova. A survey on undirected circulant graphs. Discrete Math. Algorithms Appl., 4(1), 2012.
[2] W. So. Integral circulant graphs. Discrete Mathematics, 306(1), 2006.
[3] J. W. Sander, T. Sander. On So’s conjecture for integral circulant graphs. Appl. Anal. Discrete Math., 9(1), 2015.
[4] C. M. Conde, E. Dratman, L. N. Grippo. Finding singularly cospectral graphs. Linear Multilinear Algebra, 71(3), 2023.
[5] I. Gutman. The energy of a graph: old and new results. In Algebraic combinatorics and applications (Gößweinstein, 1999), Springer, Berlin, 2001.
[6] D. Stevanović, I. Stanković. Remarks on hyperenergetic circulant graphs. Linear Algebra and its Applications, 400, 2005.
[7] S. R. Blackburn, I. E. Shparlinski. On the average energy of circulant graphs. Linear Algebra Appl., 428(8-9), 2008.