Unicyclic graphs with second largest and second smallest permanental sums

摘要

Let A(G) be an adjacency matrix of a graph G. Then the polynomial π(G,x)=per(xI−A(G)) is called the permanental polynomial of G, and the permanental sum of G is the sum of the absolute values of the coefficients of π(G, x). In this paper, the second largest and second smallest permanental sums among connected unicyclic graphs and the corresponding extremal graphs are determined. In addition, we show that the computation of permanental sum is #P-complete.