Extremal Permanents of Laplacian Matrices of Unicyclic Graphs

Abstract

The extremal problem of Laplacian permanents of graphs is a classical and challenging topic in algebraic combinatorics, where the inherent #P-complete complexity of permanent computation renders this pursuit particularly intractable. In this paper, we determine the upper and lower bounds of permanents of Laplacian matrices of unicyclic graphs, and the corresponding extremal graphs are characterized. Furthermore, we also determine the upper and lower bounds of permanents of Laplacian matrices of unicyclic graphs with given girth, and the corresponding extremal graphs are characterized.

Keywords

• Laplacian matrix
• permanent
• extremal graph
• graph parameter