Solution to an Open Problem on Laplacian Ratio

Abstract

Let G be a graph. The Laplacian ratio of G is the permanent of the Laplacian matrix of G divided by the product of degrees of all vertices. The computational complexity of Laplacian ratio is #P-complete. Brualdi and Goldwasser studied systematically the properties of Laplacian ratios of graphs. And they proposed an open problem: what is the minimum value of the Laplacian ratios of trees with n vertices having diameter at least k? In this paper, we give a solution to the problem.

Keywords

Permanent / Laplacian matrix / Laplacian ratio / tree / diameter

References

[1] BrualdiRA, GoldwasserJL. Permanent of the Laplacian matrix of trees and bipartite graphs. Discrete Math., 1984, 48(1): 1-21

[2] GengX, HuX, LiS. Further results on permanental bounds for the Laplacian matrix of trees. Linear Multilinear Algebra, 2010, 58(5–6): 571-587

[3] GengX, HuX, LiS. Permanental bounds of the Laplacian matrix of trees with given domination number. Graphs Combin., 2015, 31(5): 1423-1436

[4] GoldwasserJL. Permanent of the Laplacian matrix of trees with a given matching. Discrete Math., 1986, 61(2–3): 197-212

[5] HwangSG, ZhangXD. Permanents of graphs with cut vertices. Linear Multilinear Algebra, 2003, 51(4): 393-404

[6] LiuS. On the (signless) Laplacian permanental polynomials of graphs. Graphs Combin., 2019, 35(3): 787-803

[7] LiuX, WuT. Computing the permanental polynomials of graphs. Appl. Math. Comput., 2017, 304: 103-113

[8] ValiantLG. The complexity of computing the permanent. Theoret. Comput. Sci., 1979, 8(2): 189-201

RIGHTS & PERMISSIONS

Peking University

Just Accepted

This article has successfully passed peer review and final editorial review, and will soon enter typesetting, proofreading and other publishing processes. The currently displayed version is the accepted final manuscript. The officially published version will be updated with format, DOI and citation information upon launch. We recommend that you pay attention to subsequent journal notifications and preferentially cite the officially published version. Thank you for your support and cooperation.