| 图直径与平均距离的极值问题研究 |
| |
| 引用本文： | 周涛,徐俊明,刘隽.图直径与平均距离的极值问题研究[J].中国科学技术大学学报,2004,34(4):410-413,479. |
| |
| 作者姓名： | 周涛 徐俊明 刘隽 |
| |
| 作者单位： | 中国科学技术大学数学系,安徽合肥,230026 |
| |
| 基金项目： | 国家自然科学基金资助项目 (10 2 71114 ,10 30 10 37) |
| |
| 摘 要： | 通过研究图直径、平均距离、阶数与规模之间的约束关系，给出了Ore定理的一个简单证明，并将其推广到了有向图形式．提出了k直径图平均距离的下界定理，此定理结合Ore定理可得到只依赖于阶数和直径的图平均距离的下界，该下界好于Plesnik下界．
|
| 关 键 词： | 图论 直径 平均距离 下界 极值问题 有向图 |
| 文章编号： | 0253-2778(2004)04-0410-04 |
Extremal Problem on Diameter and Average Distance of Graphs |
| |
| ZHOU Tao,XU Jun- ming,LIU Jun.Extremal Problem on Diameter and Average Distance of Graphs[J].Journal of University of Science and Technology of China,2004,34(4):410-413,479. |
| |
| Authors: | ZHOU Tao XU Jun- ming LIU Jun |
| |
| Abstract: | The diameter and average distance of a graph are two important parameters for measuring the efficiency of interconnection networks. In the present paper, we investigate the constraint relationship among diameter, average distance, order and size of a graph. Considering that any graph can be obtained by removing some edges from a complete graph, a short proof and a counterpart for a digraph of Ore's result is given. Using a similar method, a lower bound on average distance of a graph with diameter is given, and combining this result with Ore's yields a new lower bound dependent only on the order and diameter, which is better than Plesnik's. |
| |
| Keywords: | graph theory diameter average distance lower bound extremal problem digraph |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
