On the maximal Wiener index and related questions
- 作者：Andrew V. Sills AndrewSills@GeorgiaSouthern.edu ; Hua Wang ; hwang@georgiasouthern.edu ;
- 关键词：Tree ; Wiener index ; Degree sequence
- 刊名：Discrete Applied Mathematics
- 出版年：2012
- 期刊代码：46_0166218x
- 类别：cp
- 出版时间：July, 2012
- 卷：160
- 期：10-11
- 页码：1615-1623
- 文件大小：284 K
摘要
The Wiener index of a graph is the sum of the distances between all pairs of vertices. It has been one of the main descriptors that correlate a chemical compound鈥檚 molecular structure with experimentally gathered data regarding the compound鈥檚 characteristics. In 2008, Wang and Zhang independently characterized trees with specified degree sequence that minimize the Wiener index. In the paper of Wang, a corollary on maximizing the Wiener index was pointed out to be incorrect by Zhang et. al. in 2010. Zhang et. al. also provided partial results and noted that the question turns out to be complicated. Later, 脟ela et. al. considered this question as a quadratic assignment problem and provided a polynomial time algorithm. We make some progress in this contribution, providing information on the candidate trees for the maximum Wiener index. Some interesting combinatorial relations to other objects arose from this study. We also consider the bound of this maximum value as well as study this question for trees with small diameter and for chemical trees with specified degree sequence.