Isolation of k-cliques

Abstract

For any positive integer k and any n-vertex graph G, let ι(G, k) denote the size of a smallest set D of vertices of G such that the graph obtained from G by deleting the closed neighbourhood of D contains no k-clique. Thus, ι(G, 1) is the domination number of G. We prove that if G is connected, then ι(G, k) ≤ n k+1 unless G is a k-clique, or k = 2 and G is a 5-cycle. The bound is sharp. The case k = 1 is a classical result of Ore, and the case k = 2 is a recent result of Caro and Hansberg. Our result settles a problem of Caro and Hansberg.