# Almost $K_m$-Saturated Graphs

MacDougall, James A. and Eggleton, Roger B. (1998) Almost $K_m$-Saturated Graphs. Congressus Numerantium, 131 . pp. 187-203.

 Preview
PDF - Accepted Version
A graph is $K_m$-saturated if every possible addition of an edge creates a new $m$-clique. A graph is {\em almost} $K_m$-saturated if it is maximal with respect to not being $K_m$-saturated, that is, some edge can be added without creating a new $m$-clique, but a $K_m$-saturated graph results from any possible edge addition. The structure of almost $K_m$-saturated graphs is explicitly determined, and the almost $K_m$-saturated graphs of order $n$ are enumerated for $m = 3$ and 4. A graph is {\em locally almost} $K_m$-saturated if some edge addition does not create a $K_m$ but every two edge additions do. Every graph which is almost $K_m$-saturated has this local property, but so do others: the structure of such graphs is implicitly determined.