Going critical : an investigation of diameter -critical graphs

We define a graph G=(V, E) with m=\E\ edges, n=\V\ vertices, maximum degree D, and diameter d, to be d-critical if it has the property that for any edge e G E, the graph G — e has diameter > d. We explore some results relating to a conjecture on the maximum possible number of edges in a 2-critical graph. We also present efficient algorithms for identifying spanning d-critical subgraphs of graphs having diameter d where d=2 or d=3. The algorithm for d=2 runs in 0(mn), and the algorithm for d=3 runs in 0(mnD).Science, Faculty ofMathematics, Department ofGraduat