On the permanental nullity and matching number of graphs

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.

Keywords:

• Permanental polynomial
• permanental nullity
• matching number

AMS Subject Classifications:

• 05C31
• 05C50
• 15A15

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.

Additional information

Funding

This work is supported by NSFC [grant number 11371180]; NSF of Qinghai [grant number 2016-ZJ-947Q]; High-level personnel of scientific research projects of QHMU (2016XZJ07).