Connected signed graphs with given inertia indices and given girth

Abstract

Suppose that $\hat{I}“=(G,\ddot{I}ƒ)$ is a connected signed graph with at least one cycle. The number of positive, negative and zero eigenvalues of the adjacency matrix of $\hat{I}“$ are called positive inertia index, negative inertia index and nullity of $\hat{I}“$, which are denoted by $i_{+}(\hat{I}“)$, $i_{-}(\hat{I}“)$ and $\hat{I}\cdot (\hat{I}“)$, respectively. Denoted by $g$ the girth, which is the length of the shortest cycle of $\hat{I}“$. We study relationships between the girth and the negative inertia index of $\hat{I}“$ in this article. We prove $i_{-}(\hat{I}“)\ge \lceil \frac{g}{2}\rceil -1$ and extremal signed graphs corresponding to the lower bound are characterized. Furthermore, the signed graph $\hat{I}“$ with $i_{-}(\hat{I}“)=\lceil \frac{g}{2}\rceil$ for $g\ge 4$ are given. As a by-product, the connected signed graphs with given positive inertia index, nullity and given girth are also determined, respectively.

16 pages, 5 figures