On the Laplacian coefficients of acyclic graphs (Q875026): Difference between revisions

Laplacian coefficients of a graph are the absolute values of coefficients of the characteristic polynomial of the Laplacian matrix of the graph (the vertex degree diagonal matrix minus the adjacency matrix). Two transformations are defined for trees. The \(\pi\)-transformation moves one leaf-path behind another leaf-path with the same starting node, and this is shown to be nondecreasing for all Laplacian coefficients. The \(\sigma\)-transformation moves all pending edges at some vertex except one to the other end of this latter edge, and is nonincreasing for all Laplacian coefficients. This yields an alternative proof of the result of Zhou and Gutman that stars minimize and paths maximize the Laplacian coefficients for trees of fixed size. Two consequences for the Wiener index for trees are indicated.