变更图的直径
Diameters of Altered Graphs
吴叶舟 1徐俊明1
作者信息
- 1. 中国科学技术大学数学系,安徽,合肥,230026
- 折叠
摘要
P(t,n)和C(t,n)分别表示在阶为n的路和圈中添加t条边后得到的图的最小直径;f(t,k)表示从直径为k的图中删去t条边后得到的连通图的最大直径.这篇文章证明了当t≥4且n≥5时,P(t,n)≤n-8/t+1+3;若t为奇数,则C(t,n)≤n-8/t+1+3;若t为偶数,则C(t,n)≤n-7/t+2+3.特别地,[n-1/5]≤P(4,n)≤[n+3/5],[n/4-1≤C(3,n)≤[n/4].最后,证明了:若k≥3且为奇数,则f(t,k)≥(t+1)k-2t+4.这些改进了某些已知结果.
Abstract
Let P(t, n) and C(t, n) denote the minimum diameter of a connected graph obtained from a single path and a circle of order n plus t extra edges, respectively, and f(t, k)the maximum diameter of a connected graph obtained by deleting t edges from a graph with diameter k. This paper shows that for any integers t ≥ 4 and n ≥ 5, P(t, n) ≤ n-8/t+1+3,C(t,n) ≤ n-8/t+1+3 if t is odd and C(t,n) ≤n-7/t+2+3 if t is even; [n-1/5] ≤ P(4, n) ≤[n+3/5][n/4]-1 ≤ C(3, n) ≤[n/4]; and f(t, k) ≥ (t + 1)k- 2t + 4 if k≥ 3 and is odd, which improves some known results.
关键词
直径/变更图/边增加/边减少Key words
diameter/altered graph/edge addition/edge deletion引用本文复制引用
出版年
2006
NETL
NSTL
万方数据