The extremal permanental sum for a quasi-tree graph (Q2424575)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The extremal permanental sum for a quasi-tree graph |
scientific article |
Statements
The extremal permanental sum for a quasi-tree graph (English)
0 references
25 June 2019
0 references
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\).
0 references
0 references
0 references