Diameters of Altered Graphs

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\geq4$ and $n\geq5$, $ P(t,n)\leq\frac{n-8}{t+1}+3$, $C(t,n)\leq \frac{n-8}{t+1}+3$ if $t$ is odd and $ C(t,n)\leq \frac{n-7}{t+2}+3$ if $t$ is even; $\left\lceil\frac{n-1}{5}\right\rceil\leq P(4,n)\leq\left\lceil\frac{n+3}{5}\right\rceil$, $\left\lceil\frac{n}{4}\right\rceil-1\leq C(3,n)\leq\left\lceil\frac{n}{4}\right\rceil$; and $f(t,k)\geq (t+1)k-2t+4$ if $k\geq 3$ and is odd, which improves some known results.