The nullity of the net Laplacian matrix of a signed graph

Abstract

Let $\Gamma =(G,\sigma )$ be a signed graph, where $G=(V(G),E(G))$ is an (unsigned) graph, called the underlying graph. The net Laplacian matrix of $\Gamma$ is defined as $L^{\pm }(\Gamma )=D^{\pm }(\Gamma )-A(\Gamma )$, where $D^{\pm }(\Gamma )$ and $A(\Gamma )$ are the diagonal matrix of net-degrees and the adjacency matrix of $\Gamma$, respectively. The nullity of $L^{\pm }(\Gamma )$, written as $\eta (L^{\pm }(\Gamma ))$, is the multiplicity of 0 as an eigenvalue of $L^{\pm }(\Gamma )$. In this paper, we focus our attention on the nullity of the net Laplacian matrix of a connected signed graph $\Gamma$ and prove that $1\le \eta (L^{\pm }(\Gamma ))\le min\{\beta (\Gamma )+1,|V(\Gamma )|-1\}$, where $\beta (\Gamma )=|E(\Gamma )|-|V(\Gamma )|+1$ is the cyclomatic number of $\Gamma$. The connected signed graphs with nullity $|V(\Gamma )|-1$ are completely determined. Moreover, we characterize the signed cactus graphs with nullity $1$ or $\beta (\Gamma )+1$

11 pages, 1 figures