Diameters of Altered Graphs
WU Ye-zhou, Jun‐Ming Xu · 2015
Abstract: Let P (t; n) and C(t; n) denote the minimum diameter of a connected graph ob-tained 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) n8 t+1 + 3, C(t; n) n8 t+1 + 3 if t is odd and C(t; n) n7 t+2 + 3 if t is even; n1