Two Open Problems on the Maximum Permanent of Laplacian Matrices of Trees

Abstract

In 1984, Brualdi and Goldwasser initiated a systematic study of bounds for the permanent of the Laplacian matrix of trees, proposing two open problems: characterizing its maximum value for trees with a given matching number, and determining its maximum value for trees with a given bipartition. In this paper, we resolve both problems.

Keywords

Permanent / Laplacian matrix / tree / bipartition / matching / 05C50 / 05C05 / 15A15

References

[1] Bapat RB. A bound for the permanent of the Laplacian matrix. Linear Algebra Appl., 1986, 74: 219-223.

[2] Botti P, Merris R, Vega C. Laplacian permanents of trees. SIAM J. Discrete Math., 1992, 54460466.

[3] Brouwer AE, Haemers WH. Spectra of Graphs. Universitext, 2012, New York: Springer

[4] Brualdi RA, Goldwasser JL. Permanent of the Laplacian matrix of trees and bipartite graphs. Discrete Math., 1984, 481121.

[5] Cauchy AL. Cours d’analyse de l’École Royale Polytechnique, Premiere Partie, Instrumenta Rationis. Sources for the History of Logic in the Modern Age, VII, 1992, Bologna: Coop. Lib. Univ.

[6] Cvetković DM, Doob M, Sachs H. Spectra of Graphs, 1995Third EditionHeidelbergJohann Ambrosius Barth

[7] Geng X, Hu X, Li S. Further results on permanental bounds for the Laplacian matrix of trees. Linear Multilinear Algebra, 2010, 585–6571587.

[8] Geng X, Hu S, Li S. Permanental bounds of the Laplacian matrix of trees with given domination number. Graphs Combin., 2015, 31514231436.

[9] Goldwasser JL. Permanent of the Laplacian matrix of trees with a given matching. Discrete Math., 1986, 612–3197212.

[10] Li S, Li Y, Zhang X. Edge-grafting theorems on permanents of the Laplacian matrices of graphs and their applications. Electron. J. Linear Algebra, 2013, 26: 28-48.

[11] Liu SY. On the (signless) Laplacian permanental polynomials of graphs. Graphs Combin., 2019, 353787803.

[12] Liu XG, Wu TZ. Computing the permanental polynomials of graphs. Appl. Math. Comput., 2017, 304: 103-113

[13] Lovász L, Plummer MD. Matching Theory, 1986, Amsterdam: North-Holland29

[14] Merris R. The Laplacian permanental polynomial for trees. Czechoslovak Math. J., 1982, 323397403.

[15] Merris R, Rebman KR, Watkins WE. Permanental polynomials of graphs. Linear Algebra Appl., 1981, 38: 273-288.

[16] Valiant LG. The complexity of computing the permanent. Theoret. Comput. Sci., 1979, 82189201.

[17] Vrba A. The permanent of the Laplacian matrix of a bipartite graph. Czechoslovak Math. J., 1986, 361717.

[18] Wu T.Z., Dong X., Further results on permanents of Laplacian matrices of trees. Open Math., 2025, 23(1): Paper No. 20250185, 19 pp.

[19] Wu TZ, Dong X, Lai H, Zeng X. Solution to an open problem on Laplacian ratio. Front. Math., 2016, 214815837.

[20] Xu JM. Theory and Application of Graphs, 2003, Dordrecht: Kluwer Acad. Publ.10

Rights & permissions

Peking University