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 / 05C05 / 05C50 / 15A15

References

[1] Brualdi RA, Goldwasser JL. Permanent of the Laplacian matrix of trees and bipartite graphs. Discrete Math., 1984, 48(1): 1-21.

[2] Geng X, Hu X, Li S. Further results on permanental bounds for the Laplacian matrix of trees. Linear Multilinear Algebra, 2010, 58(5–6): 571-587.

[3] Geng X, Hu X, Li S. Permanental bounds of the Laplacian matrix of trees with given domination number. Graphs Combin., 2015, 31(5): 1423-1436.

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

[5] Hwang SG, Zhang XD. Permanents of graphs with cut vertices. Linear Multilinear Algebra, 2003, 51(4): 393-404.

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

[7] Liu X, Wu T. Computing the permanental polynomials of graphs. Appl. Math. Comput., 2017, 304: 103-113

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

RIGHTS & PERMISSIONS

Peking University