Skip to main content
Article
Extremal Trees with Given Degree Sequence for the Randić Index
Discrete Mathematics (2008)
  • Hua Wang, Georgia Southern University
Abstract
The Randić index of a graph G is the sum of ((d(u))(d(v)))α over all edges uv of G, where d(v) denotes the degree of v in G, α≠0. When α=1, it is the weight of a graph. Delorme, Favaron, and Rautenbach characterized the trees with a given degree sequence with maximum weight, where the question of finding the tree that minimizes the weight is left open. In this note, we characterize the extremal trees with given degree sequence for the Randić index, thus answering the same question for weight. We also provide an algorithm to construct such trees.
Keywords
  • Randić index,
  • Weight,
  • Degree sequence
Disciplines
Publication Date
August 6, 2008
DOI
10.1016/j.disc.2007.06.026
Citation Information
Hua Wang. "Extremal Trees with Given Degree Sequence for the Randić Index" Discrete Mathematics Vol. 308 Iss. 15 (2008) p. 3407 - 3411 ISSN: 0012-365X
Available at: http://works.bepress.com/hua_wang/2/