𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Trees with minimal Laplacian coefficients

✍ Scribed by Aleksandar Ilić


Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
408 KB
Volume
59
Category
Article
ISSN
0898-1221

No coin nor oath required. For personal study only.

✦ Synopsis


Let G be a simple undirected graph with the characteristic polynomial of its Laplacian matrix L(G), P(G, µ) = n k=0 (-1) k c k µ n-k . It is well known that for trees the Laplacian coefficient c n-2 is equal to the Wiener index of G, while c n-3 is equal to the modified hyper-Wiener index of the graph. In this paper, we characterize n-vertex trees with given matching number m which simultaneously minimize all Laplacian coefficients. The extremal tree A(n, m) is a spur, obtained from the star graph S n-m+1 with n -m+1 vertices by attaching a pendant edge to each of certain m -1 non-central vertices of S n-m+1 . In particular, A(n, m) minimizes the Wiener index, the modified hyper-Wiener index and the recently introduced Incidence energy of trees, defined as IE(G) = n k=0 √ µ k , where µ k are the eigenvalues of signless Laplacian matrix Q (G) = D(G) + A(G). We introduced a general ρ transformation which decreases all Laplacian coefficients simultaneously. In conclusion, we illustrate on examples of Wiener index and Incidence energy that the opposite problem of simultaneously maximizing all Laplacian coefficients has no solution.


📜 SIMILAR VOLUMES