Inertia indices of signed graphs with given cyclomatic number and given number of pendant vertices

Abstract

Let $\Gamma =(G,\sigma )$ be a signed graph of order $n$ with underlying graph $G$ and a sign function $\sigma :E(G)\to \{+,-\}$. Denoted by $i_{+}(\Gamma )$, $\theta (\Gamma )$ and $p(\Gamma )$ the positive inertia index, the cyclomatic number and the number of pendant vertices of $\Gamma$, respectively. In this article, we prove that $i_{+}(\Gamma )$, $\theta (\Gamma )$ and $p(\Gamma )$ are related by the inequality $i_{+}(\Gamma )\ge \frac{n-p(\Gamma )}{2}-\theta (\Gamma )$. Furthermore, we completely characterize the signed graph $\Gamma$ for which $i_{+}(\Gamma )=\frac{n-p(\Gamma )}{2}-\theta (\Gamma )$. As a by-product, the inequalities $i_{-}(\Gamma )\ge \frac{n-p(\Gamma )}{2}-\theta (\Gamma )$ and $\eta (\Gamma )\le p(\Gamma )+2\theta (\Gamma )$ are also obtained, respectively.