On the permanental nullity and matching number of graphs

Abstract

For a graph $G$ with $n$ vertices, let $\nu (G)$ and $A(G)$ denote the matching number and adjacency matrix of $G$, respectively. The permanental polynomial of $G$ is defined as $\pi (G,x)=\mathrm{per}(Ix-A(G))$. The permanental nullity of $G$, denoted by ${\eta }_{per}(G)$, is the multiplicity of the zero root of $\pi (G,x)$. In this paper, we use the Gallai-Edmonds structure theorem to derive a concise formula which reveals the relationship between the permanental nullity and the matching number of a graph. Furthermore, we prove a necessary and sufficient condition for a graph $G$ to have ${\eta }_{per}(G)=0$. As applications, we show that every unicyclic graph $G$ on $n$ vertices satisfies $n-2\nu (G)-1\le {\eta }_{per}(G)\le n-2\nu (G)$, that the permanental nullity of the line graph of a graph is either zero or one, and that the permanental nullity of a factor critical graph is always zero.