On graphs that are critical with respect to the parameters: diameter, connectivity and edge-connectivity

  • Lou Caccetta


In graph theory, the term critical is usually used with respect to specified graph parameter P and applies when the graph G under consideration has the property P but alteration of G (such as vertex deletion, edge deletion or edge addition) result in a graph not having property P. In this paper, we consider graphs which are critical with respect to parameter P under the single operation of: deleting a vertex; deleting an edge; adding an edge. In particular, we focus on the graph parameters: diameter, connectivity and edge-connectivity. We review important results and mention many open problems.