Isolation of connected graphs

Abstract

For a connected n-vertex graph G and a positive integer k, let ιk(G) 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 connected graph that has at least k edges. By a result of Caro and Hansberg, ι1(G) ≤ n/3 if n ̸= 2 and G is not a 5-cycle. Let r be the number of vertices of G that have only one neighbour. We show that ι2(G) ≤ (4n−r)/14 if G is not a copy of one of six graphs. We also show that ι3(G) ≤ n/4 if G is neither a triangle nor a 7-cycle. The bounds are sharp. The two new results imply recent results on isolation of graphs. The bound on ι3(G) strengthens the author’s solution to a problem of Caro and Hansberg on isolation of cycles.