caa a22 4500 475777948 CHVBK 20180406123636.0 cr unu---uuuuu 170329e20000301xx s 000 0 eng 10.1007/s003730050002 doi (NATIONALLICENCE)springer-10.1007/s003730050002 Closure Concepts: A Survey [Elektronische Daten] [Hajo Broersma, Zdeněk Ryjáček, Ingo Schiermeyer] Abstract. : 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 Bondy and Chvátal 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 G+uv is hamiltonian if and only if G is hamiltonian. Based on this result, they defined the n-closure cln (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 cln(G) is well-defined, and that G is hamiltonian if and only if cln(G) is hamiltonian. Moreover, they showed that cln(G) can be obtained by a polynomial algorithm, and that a Hamilton cycle in cln(G) can be transformed into a Hamilton cycle of G by a polynomial algorithm. As a consequence, for any graph G with cln(G)=K n (and n≥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, Bondy and Chvátal 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. Springer-Verlag Tokyo, 2000 Broersma Hajo Faculty of Mathematical Sciences, University of Twente, P.O. Box 217, 7500 AE Enschede, the Netherlands. e-mail: broersma@math.utwente.nl, NL aut Ryjáček Zdeněk Department of Mathematics, University of West Bohemia, P.O. Box 314, 306 14 Plzeň, Czech Republic. e-mail: ryjacek@kma.zcu.cz, CZ aut Schiermeyer Ingo Department of Mathematics, Technical University of Freiberg, D-09596 Freiberg, Germany. e-mail: schierme@math.tu-freiberg.de, DE aut https://doi.org/10.1007/s003730050002 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s003730050002 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Broersma Hajo Faculty of Mathematical Sciences, University of Twente, P.O. Box 217, 7500 AE Enschede, the Netherlands. e-mail: broersma@math.utwente.nl, NL aut NATIONALLICENCE 700 1- Ryjáček Zdeněk Department of Mathematics, University of West Bohemia, P.O. Box 314, 306 14 Plzeň, Czech Republic. e-mail: ryjacek@kma.zcu.cz, CZ aut NATIONALLICENCE 700 1- Schiermeyer Ingo Department of Mathematics, Technical University of Freiberg, D-09596 Freiberg, Germany. e-mail: schierme@math.tu-freiberg.de, DE aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer