On addition and deletion of edges of graphs
Najim Alaa · 2006
Let P(t,d)(resp.C(t,d)) denote the minimum diameter of a graph obtained by adding t extra edges to a path(resp.cycle) of length d.Let T_P(p,d)(resp.T_C(p,d)) be the minimum number of edges added to a path(resp.cycle) of length d in order to obtain a graph of diameter not greater than p.Let f(t,d) denote the maximum diameter of a connected graph obtained after deleting t edges from a connected graph of diameter d.Some new lower and upper bounds of these parameters were presented.In particular,it is proved that T_C(3,d)=d-8 for d≥12 conjectured by Grigorescu [J.Graph Theory,2003,43(2):299-303],and it is partially proved that f(t,d)≤((t+1)d-)t+1 conjectured by Schoone et al [J.Graph Theory,1987,11(3):409-427].