首页 | 本学科首页   官方微博 | 高级检索  
     检索      

变更图的直径
引用本文:邓志国,徐俊明.变更图的直径[J].数学研究,2004,37(1):35-41.
作者姓名:邓志国  徐俊明
作者单位:中国科技大学,安徽,合肥,230026
基金项目:Thework was supported by NNSF of China (1 0 2 71 1 1 4 )
摘    要:对于给定的正整数t和d(≥2),用F(t,d)和P(t,d)分别表示在所有直径为d的图和路中添加t条边后得到的图的最小直径,用f(t, d)表示从所有直径为d的图中删去t条边后得到的图的最大直径. 已经证明P(1, d)=(d)/(2), P(2,d)=(d 1)/(3)和P(3, d)=(d 2)/(4). 一般地,当t和d≥4时有(d 1)/(t 1)-1≤P(t, d)≤(d 1)/(t 1) 3. 在这篇文章中,我们得到F(t, f(t, d))≤d≤f(t, F(t, d))和(d)/(t 1)≤F(t, d)=P(t, d)≤(d-2)/(t 1) 3,而且当d充分大时,F(t, d)≤(d)/(t) 1. 特别地,对任意正整数k有P(t, (2k-1)(t 1) 1)=2k,当t=4或5,且d≥4时有(d)/(t 1)≤P(t, d)≤(d)/(t 1) 1.

关 键 词:直径    变更图    边增加    边减少

On Diameters of Altered Graphs
Abstract.On Diameters of Altered Graphs[J].Journal of Mathematical Study,2004,37(1):35-41.
Authors:Abstract
Abstract:For given positive integers t and d(≥2), let F(t,d) and P(t,d) denote the minimum diameter of a graph obtained by adding t extra edges to a graph and a path with diameter d, respectively, and f(t, d) denote the maximum diameter of a graph obtained after deleting t edges from a graph with diameter d. It is known that P(1, d)=(d+1)/(2) for d≥2, P(2, d)=(d+1)/(3) for d≥3, P(3, d)=(d+2)/(4) if d≥5, and, in general, (d+1)/(t+1)-1≤P(t,d)<(d+1)/(t+1)+3 for t, d≥4. In the present paper, we establish F(t, f(t, d))≤d≤f(t, F(t, d)) and prove (d)/(t+1)≤F(t, d)=P(t, d)≤(d-2)/(t+1)+3. Moreover, F(t, d)≤(d)/(t)+1 if d is large enough. In particular, we derive the exact values P(t, (2k-1)(t+1)+1)=2k for any positive integer k, and (d)/(t+1)≤P(t, d)≤(d)/(t+1)+1 for t=4 or 5 and d≥4.
Keywords:Diameter  Altered graph  Edge addition  Edge deletion
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号