Menu
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.