On the Wiener index and Laplacian coefficients of graphs with given diameter or radius

preprint2011arXivOpen access

Abstract

Let GG be a simple undirected nn-vertex graph with the characteristic polynomial of its Laplacian matrix L(G)L(G), det⁡(λI−L(G))=∑k=0n(−1)kckλn−k\det (λI - L (G))=\sum_{k = 0}^n (-1)^k c_k λ^{n - k}. It is well known that for trees the Laplacian coefficient cn−2c_{n-2} is equal to the Wiener index of GG. Using a result of Zhou and Gutman on the relation between the Laplacian coefficients and the matching numbers in subdivided bipartite graphs, we characterize first the trees with given diameter and then the connected graphs with given radius which simultaneously minimize all Laplacian coefficients. This approach generalizes recent results of Liu and Pan [MATCH Commun. Math. Comput. Chem. 60 (2008), 85--94] and Wang and Guo [MATCH Commun. Math. Comput. Chem. 60 (2008), 609--622] who characterized nn-vertex trees with fixed diameter dd which minimize the Wiener index. In conclusion, we illustrate on examples with Wiener and modified hyper-Wiener index that the opposite problem of simultaneously maximizing all Laplacian coefficients has no solution.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.