具有最小及次小Wiener指数的极值树.pdf

第32 卷第2 期 丽 水 学 院 学 报 2010 年4 月 Vo1.32 No.2 JOURNAL OF LISHUI UNIVERSITY Apr.2010 具有最小及次小Wiener 指数的极值树 陈娅红 （丽水学院 教育学院，浙江 丽水323000 ） 摘要：利用度序列的优超偏序关系，分别刻画了给定匹配数或独立数的具有最小和次小Wiener 指数的n 阶极值树特征。 关键词：Wiener 指数；极值树；匹配数；独立数；阶数 doi ：10.3969/j.issn.1008-6749.2010.02.002 中图分类号：O157.5 文献标志码：A 文章编号：1008-6749 （2010）02-0004- 03 Extremal Trees with the Minimum and the Second Minimum Wiener Indices Chen Yahong （College of Education ，Lishui University，Lishui Zhejiang 323000 ，China ） Abstract ：In this pa per ，by using the majorization partial ordering of degree sequences ，the author characterized the extremal trees with the minimum and the second minimum Wiener indices among all the n- vertex trees with given matching number or independent number respectively. Key words ：Wiener index ；extremal tree ；matching number ；independent number ；order 0 引言及预备知识 W （G）＝ Σ dG （u ，v）。 Wiener 指数是化学图论中经典的拓扑指数之 u，v V （G） [1- 3] 若M 为E （G）的一个子集且M 中任意两条边 一 ，它表示图中任意两点间距离之和。它是在研 究化学分子结构模型中提出的重要概念，并已被 不相邻，则称M 为G 的一个匹配。若不存在G 的 证实它能够揭示化学中分子之间的性能关系。 另一个匹配M ′使得 M ′ ＞ M ，则称M 为G 的一 个最大匹配，此时 称为G 的匹配数。若 U 为 本文所涉及到的图都是连通的简单无向图。 M 一个图G 的顶点集和边集分别为V （G）和E （G）， V （G）的一个子集且U 中任意两个顶点不相邻，则 G 的顶点数（也称为G 的阶数）和边数分别用 称U 为G 的一个独立集。若不存在G 的另一个独 和 表示。顶点u 和v 的距离d （u，v） 立集U′使得 U′ ＞ U ，则称U 为G 的最大独立 V （G） E （G） G 表示图G 中连接u，v 的最短路长度。一个图G 的