CAJ | 학술논문

对于给定的正整数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.
대우급정적정정수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.
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.