Extremal trees with given degree sequence for the Randić index
- 作者：Hua Wang
- 关键词：Tree ; Randić ; index ; Weight ; Degree sequence
- 刊名：Discrete Mathematics
- 出版年：2008
- 期刊代码：47_0012365x
- 类别：cp
- 出版时间：6 August 2008
- 卷：308
- 期：15
- 页码：3407-3411
- 文件大小：316 K
摘要
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.
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.