The Effects of Vertex and Edge Deletion on Graphs

Abstract

Many different approaches exist in studying graphs with high connectivity and small diameter. We consider the effect of deleting vertices and edges from a graph while maintaining a small diameter. The following property is introduced: A graph $G$ has property $B_{d,i,j}$ if and only if after the removal of at most $i$ vertices and at most $j$ edges, the resulting graph has diameter at most $d$ and is not the trivial graph on one vertex. The central theme of this paper is to investigate the structure of graphs that have property $B_{d,i,j}$ and to investigate the structure that is needed to imply that a graph has property $B_{d,i,j}$. Lower bounds on minimum degree and connectivity that imply property $B_{d,i,j}$ for specific values of $d$ are found. These bounds are also shown to be sharp in all but one case.