All minimum C5-saturated graphs

Abstract

A graph is C5- saturated if it has no five-cycle as a subgraph, but does contain a C5 after the addition of any new edge. Extending our previous result, we prove that the minimum number of edges in a C5-saturated graph on n vertices is sat(n, C5) = ⌈10(n − 1)/7⌉ − 1 for 11≤n≤14, or n = 16, 18, 20, and is ⌈10(n − 1)/7⌉ for all other n≥5, and we also prove that the only C5-saturated graphs with sat(n, C5) edges are the graphs described in Section 2. © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 9-26, 2011