The extremal permanental sum for a quasi-tree graph (Q2424575)

Summary: Let \(G\) be a graph and \(A(G)\) the adjacency matrix of \(G\). The permanent of matrix \((x I - 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 \leq m \leq 2 n - 3\).