运筹学学报 ›› 2010, Vol. 14 ›› Issue (2): 55-60.

• 运筹学 • 上一篇    下一篇

若干图类的Wiener指数的极值

林晓霞   

  • 出版日期:2010-06-15 发布日期:2010-06-15

On the Extremal Wiener Indices of Some Graphs

LIN Xiao-Xia   

  • Online:2010-06-15 Published:2010-06-15

摘要: 一个图的Wiener指数是指这个图中所有点对的距离和. Wiener指数在理论化学中有广泛应用. 本文刻画了给定顶点数及特定参数如色数或团数的图中Wiener指数达最小值的图, 同时也刻画了给定顶点数及团数的图中Wiener指数达最大值的图.  

Abstract:  The Wiener index of a graph is defined as the sum of distances between all pairs of vertices of the graph. It has been found extensive applications in chemistry. In this paper, we characterize the graphs which minimize the Wiener index among all graphs with given order and specific parameter, such as the chromatic number or clique number, and the graphs which maximize the Wiener index among all graphs with given order and clique number.