Authors: Stevanović, Dragan 
Title: Maximizing Wiener index of graphs with fixed maximum degree
Journal: Match
Volume: 60
Issue: 1
First page: 71
Last page: 83
Issue Date: 10-Jul-2008
Rank: M21a
ISSN: 0340-6253
The Wiener index of a graph is the sum of all pairwise distances of vertices of the graph. Fischermann et al [5] characterized the trees which minimize the Wiener index among all trees with the maximum degree at most Δ. They also determined the trees which maximize the Wiener index, but in a much more restricted family of trees which have two distinct vertex degrees only. In this note, we fully solve the latter problem and determine the trees which maximize the Wiener index among all graphs with the maximum degree Δ. We also determine all graphs whose Wiener index differs by less than n - Δ from the maximum value.
Publisher: Faculty of Sciences, University of Kragujevac
Project: Serbian Ministry of Science and Environmental Protection, research grant 144015G
Slovenian Agency for Research, program P1-0285

Show full item record


checked on May 23, 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.