The graphs whose permanental polynomials are symmetric
Discussiones Mathematicae Graph Theory
Received 16.05.2016, Revised 16.05.2016, Accepted 07.11.2016, doi: 10.7151/dmgt.1986
The permanental polynomial π(G,x)=∑i=0nbixn-i of a graph G is symmetric if bi=bn-i for each i. In this paper, we characterize the graphs with symmetric permanental polynomials. Firstly, we introduce the rooted product H(K) of a graph H by a graph K, and provide a way to compute the permanental polynomial of the rooted product H(K). Then we give a sufficient and necessary condition for the symmetric polynomial, and we prove that the permanental polynomial of a graph G is symmetric if and only if G is the rooted product of a graph by a path of length one.
permanental polynomial, rooted product, matching