Abstract
For a graph G with n vertices, let and A(G) denote the matching number and adjacency matrix of G, respectively. The permanental polynomial of G is defined as
. The permanental nullity of G, denoted by
, is the multiplicity of the zero root of
. 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
. As applications, we show that every unicyclic graph G on n vertices satisfies
, 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.
Acknowledgements
The authors would like to thank the anonymous referees for carefully reading the manuscript and giving valuable suggestions.
Notes
No potential conflict of interest was reported by the authors.