Edge addition and edge deletion of graphs
Najim Alaa · 2006
Let P(t,d)(resp.C(t,d)) be the minimum diameter of a connected graph obtained from a single path(resp.from a single circle) of length d by adding t extra edges.It is proved that P(t,d)=d-2t+1+1 if t and d satisfy the following conditions: t≥4 and t+4≤d≤t+7,t=4 and d=10k+1(k≥1).For some t and d,the exact value and the best lower bound of C(t,d) are determined,and so the conjecture of Schoone,et al [J.Graph Theory,1987,11:409-427] is settled partially.