The Extremal Permanental Sum for a Quasi-Tree Graph

Abstract EN

Let G be a graph and A(G) the adjacency matrix of G.

The permanent of matrix (xI-A(G)) is called the permanental polynomial of G.

The permanental sum of G is the sum of the absolute values of the coefficients of permanental polynomial of G.

Computing the permanental sum is #p-complete.

In this note, we prove the maximum value and the minimum value of permanental sum of quasi-tree graphs.

And the corresponding extremal graphs are also determined.

Furthermore,we also determine the graphs with the minimum permanental sum among quasi-tree graphs of order n and size m, where n-1≤m≤2n-3.