Mathematics – Combinatorics
Scientific paper
2011-05-29
MATCH Commun. Math. Comput. Chem. 63 (2010) 91-100
Mathematics
Combinatorics
10 pages, 5 figures
Scientific paper
Let $G$ be a simple undirected $n$-vertex graph with the characteristic polynomial of its Laplacian matrix $L(G)$, $\det (\lambda I - L (G))=\sum_{k = 0}^n (-1)^k c_k \lambda^{n - k}$. It is well known that for trees the Laplacian coefficient $c_{n-2}$ is equal to the Wiener index of $G$. 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 $n$-vertex trees with fixed diameter $d$ 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.
Ilic Aleksandar
Ilic Andreja
Stevanović Dragan
No associations
LandOfFree
On the Wiener index and Laplacian coefficients of graphs with given diameter or radius does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Wiener index and Laplacian coefficients of graphs with given diameter or radius, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Wiener index and Laplacian coefficients of graphs with given diameter or radius will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-676994