The Extremal Permanental Sum for a Quasi-Tree Graph. (20th May 2019)

• Record Type: Journal Article
• Authors: Wu, Tingzeng; Lü, Huazhong
• Other Names: Volchenkov Dimitri Academic Editor.
• Is Part Of: Complexity. Volume 2019(2019)
• Publication Date: 2019-05-20
• Subjects: Chaotic behavior in systems -- Periodicals; Complexity (Philosophy) -- Periodicals; 003
• DOI: 10.1155/2019/4387650
• Languages: English
• ISSNs: 1076-2787

Abstract

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 .