P3-connected graphs of minimum size

Abstract

cted. For example, P k for k 3 has diameter k and yet is not P k -connected. Let C k be a cycle with k edges. A graph without C k as a (not necessarily induced) subgraph is called C k -free. A C k -saturated graph is a maximal C k - free graph in the sense that adding any edge creates a C k . If adding an edge between two nodes creates a C k , then a P k\\Gamma1 must connect the nodes. So a C k -saturated graph is P k\\Gamma1 -connected. However, a P k\\Gamma1 -connected graph need not be C k -saturated (e.g., Figure 3 (d) and (e)). Assume throughout that n is the number of nodes and e is the num