Sesión Matemática DiscretaSobre el radio espectral de los grafos bipartitos con signo no balanceados
Luciano N. Grippo
Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. CONICET, ICI-UNGS, Buenos Aires, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Un \emph{grafo con signo} $\dot\Sigma$ consiste en un grafo $\Sigma=(V,E)$, llamado \emph{grafo subyacente}, y una función signo $\sigma:\, E\to\{-1,1\}$. Con $(\dot\Sigma,H^-)$ denotamos al grafo con signo $\dot\Sigma$ cuyas aristas $e$ negativas ($\sigma(e)=-1$) inducen un grafo $H$. Una matriz de adyacencia $A(\dot\Sigma)$ de $\dot\Sigma$ es una matriz cuyas filas y respectivas columnas están indexadas por algún ordenamiento de $V$; $A(\dot\Sigma)_{uv}$ es igual a $0$, $-1$ y $1$ si $uv\notin E$, $\sigma(uv)=-1$ y $\sigma(uv)=1$, respectivamente. Consideremos sus autovalores: $\lambda_1(\dot\Sigma)\ge\cdots\ge\lambda_n(\dot\Sigma)$ ordenados de mayor a menor, donde $n=|V|$. Un grafo con signo es balanceado si todos sus ciclos tienen una cantidad par de aristas negativas. Es bien conocida la siguiente relación entre los índices del grafo con signo y su correspondiente grafo subyacente: $\lambda_1(\dot\Sigma)\le \lambda_1(\Sigma)$; valiendo la igualdad solo en el caso de que $\dot\Sigma$ sea balanceado. Cabe mencionar que, en el caso que $\Sigma$ sea bipartito, el radio espectral y el índice de $\dot\Sigma$ coinciden, es decir: $\max\{-\lambda_n(\dot\Sigma),\lambda_1(\dot\Sigma)\}=\rho(\dot\Sigma)=\lambda_1(\dot\Sigma)$. Los grafos con signo fueron introducidos por Harary en 1953 en el contexto de la psicología social. En 2022, Brunetti y Stanić caracterizaron los grafos conexos con signo no balanceados con orden, tamaño, y número de vértices fijos con máximo índice y radio espectral, respectivamente. Koledin y Stanić iniciaron esta línea de investigación en 2017, conjecturando que si $\dot\Sigma$ es un grafo completo con signo no balanceado de máximo índice, con $n$ vértices y $k$ aristas negativas, siendo $k \lt n-1$, entonces el conjunto de aristas negativas inducen la estrella $K_{1,k-1}$. En 2021, Ghorbani y Mjidi confirmaron esta conjetura. En un artículo reciente, Li, Lin, y Meng caracterizaron los grafos completos con signo no balanceados de máximo radio espectral, cuyas aristas negativas inducen un árbol generador. Nuestro trabajo se inspira en estos artículos previos mencionados. Específicamente, caracterizamos los grafos bipartitos completos con signo no balanceados $(K_{r,s},H^-)$, donde $H$ es un árbol con $k$ aristas tales que $k\le\max\{\frac r 2-1,\frac s 2-1\}$. Además, caracterizamos los grafos bipartitos con signo no balanceados con $n$ vértices de máximo radio espectral.
Trabajo en conjunto con: Ezequiel Dratman (Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. CONICET, ICI-UNGS, Buenos Aires, Argentina) y Cristian M. Conde (Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. CONICET, ICI-UNGS, Buenos Aires, Argentina).