Closure concepts:: A survey

In this paper we survey results of the following type (known as closure results). Let P be a graph property, and let C(u, v) be a condition on two nonadjacent vertices u and v of a graph G. Then G + uv has property P if and only if G has property P. The first and now well-known result of this type was established by Bendy and Chvatal in a paper published in 1976: If u and v are two nonadjacent vertices with degree sum n in a graph G on n vertices, then C + uv is hamiltonian if and only if G is hamiltonian. Based on this result, they defined the n-closure cl(n)(G) of a graph G on n vertices as the graph obtained from G by recursively joining pairs of nonadjacent vertices with degree sum n until no such pair remains. They showed that cl(n)(G) is well-defined, and that G is hamiltonian if and only if cl(n)(G) is hamiltonian. Moreover, they showed that cl(n)(G) can be obtained by a polynomial algorithm, and that a Hamilton cycle in cl(n)(G) can be transformed into a Hamilton cycle of C by a polynomial algorithm. As a consequence, for any graph G with cl(n)(G) = K-n (and n greater than or equal to 3), a Hamilton cycle can be found in polynomial time, whereas this problem is NP-hard for general graphs. All classic sufficient degree conditions for hamiltonicity imply a complete n-closure, so the closure result yields a common generalization as well as an easy proof for these conditions. In their first paper on closures, Bendy and Chvatal gave similar closure results based on degree sum conditions for nonadjacent vertices for other graph properties. Inspired by their first results, many authors developed other closure concepts for a variety of graph properties, or used closure techniques as a tool for obtaining deeper sufficiency results with respect to these properties. Our aim is to survey this progress on closures made in the past (more than) twenty years.