##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 451.05040

**Autor: ** Erdös, Paul; Harary, Frank; Klawe, Maria

**Title: ** Residually-complete graphs. (In English)

**Source: ** Ann. Discrete Math. 6, 117-123 (1980).

**Review: ** If G is a graph such that the deletion from G of the points in saech closed neighborhood results in the complete graph K_{n}, then we say that G is K_{n}-residual. Simularly, if the removal of m consecutive closed neighborhoods yields K_{n}, then G is called m-K_{n}-residual. We determine the minimum order of the m-K_{n}-residual graphs for all m and n. It is further shown that for n \geq 2, K_{n+1}× K_{2} is a connection K_{2}-residual graph of minimum order and that, for n \geq 5, it is the only such graph. For n = 3 and n = 4 there i one other such graph and for n = 2, C_{5} is the only such graph.

**Reviewer: ** R.L.Hemminger

**Classif.: ** * 05C99 Graph theory

05C35 Extremal problems (graph theory)

**Keywords: ** complete graphs; residual graphs

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag