The Extremal Permanental Sum for a Quasi-Tree Graph. (20th May 2019) - Wu, Tingzeng; Lü, Huazhong
Abstract : LetG be a graph andA ( G ) the adjacency matrix ofG . The permanent of matrix( x I - A ( G ) ) is called the permanental polynomial ofG . The permanental sum ofG is the sum of the absolute values of the coefficients of permanental polynomial ofG . 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 ordern and sizem, wheren - 1 ≤ m ≤ 2 n - 3 .