Computing the permanental polynomials of graphs

摘要

Let M be an n × n matrix with entries mij (i,j=1,2,…,n). The permanent of M is defined to be per(M)=∑σ∏i=1nmiσ(i),where the sum is taken over all permutations σ of {1,2,…,n}. The permanental polynomial of M is defined by per(xIn−M), where In is the identity matrix of size n. In this paper, we give recursive formulas for computing permanental polynomials of the Laplacian matrix and the signless Laplacian matrix of a graph, respectively.