Sobre el radio espectral de los grafos de bloques.

CONDE, CRISTIAN M.; DRATMAN, EZEQUIEL; GRIPPO, LUCIANO N.

Congreso; VirtUMA 2020; 2020

El problema de buscar grafos que maximicen o minimicen el radio espectralen una familia de grafos H con n vértices, ha llamado la atención en el área de la teoría espectral de grafos. Este tipo de problemas suelen resolverse utilizando transformaciones dentro de la familia H que tienen un comportamiento monótono en relación al radio espectral. Más información sobre estás técnicas, y otras, se pueden encontrar en [1]. En [2], Lovász and Pelikán demuestran que el único grafo que maximiza el radio espectral entre los árboles con n vértices es la estrella K_{1,n−1}y el único grafo con radio espectral mínimo es el camino P_n.Es sabido que agregar aristas a un grafo incrementa el radio espectral, porlo tanto, si H contiene grafos completos y caminos, entonces K_n maximiza y P_n minimiza ρ(G) en H, de donde se deduce que estos dos grafos tienen el mínimo y el máximo radio espectral cuando H es la clase de todos los grafos conexos con n vértices. Ante esta situación, muchos autores consideran este problema en familias H que no contengan caminos o grafos completos, definidas a partir de cierta restricción de algún parámetro clásico de la teoría de grafos. Se podría considerar el trabajo [3], de Brualdi y Solheid, como una piedra fundacional en el estudio de estos problemas.En esta charla vamos a considerar dos subfamilias de grafos de bloques con n vértices, los grafos de bloques con tamaño máximo de conjunto independiente dado, y los grafos de bloques con todos los bloques de igual tamaño. Para ambas subfamilias mostraremos que hay un único grafo que maximiza el radio espectral y obtendremos cotas superiores ajustadas para ρ(G). Además, en la segunda subfamilia, mostraremos que hay un único grafo que minimiza el radio espectral y obtendremos cotas inferiores para ρ(G).[1] D. Stevanovic̀. Spectral radius of graphs. Academic Press, 2014.[2] L. Lováz, J. Pelikán. On the eigenvalues of trees. Period. Math. Hungar. 3 (1973) 175?182.[3] R. A. Brualdi, E. S. Solheid. On the spectral radius of complementary acyclic matrices of zeros and ones. SIAM J Algebra Discrete Method 7 (1986) 265?272.