Authors: Ilić, Aleksandar
Ilić, Andreja
Stevanović, Dragan 
Title: On the wiener index and laplacian coefficients of graphs with given diameter or radius
Journal: Match
Volume: 63
Issue: 1
First page: 91
Last page: 100
Issue Date: 16-Jul-2010
Rank: M21a
ISSN: 0340-6253
Let G be a simple undirected n-vertex graph with the characteristic polynomial of its Laplacian matrix L(G), det(λI - L(G)) = Σk=0n (-1)kckλ 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.
Publisher: Faculty of Sciences, University of Kragujevac
Project: Slovenian Agency for Research, program P1-0285
Serbian Ministry of Science, Grant no. 144015G

Show full item record


checked on Jun 16, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.