Isolation of regular graphs and k-chromatic graphs

Abstract

Given a set F of graphs, we call a copy of a graph in F an F-graph. The F-isolation number of a graph G, denoted by ι(G, F), is the size of a smallest set D of vertices of G such that the closed neighborhood of D intersects the vertex sets of the F-graphs contained by G (equivalently, G−N[D] contains no F-graph). Thus, ι(G, {K1}) is the domination number of G. For any integer k ≥ 1, let F1,k be the set of regular graphs of degree at least k−1, let F2,k be the set of graphs whose chromatic number is at least k, and let F3,k be the union of F1,k and F2,k. Thus, k-cliques are members of both F1,k and F2,k. We prove that for each i ∈ {1, 2, 3}, m+1 ( k 2)+2 is a best possible upper bound on ι(G, Fi,k) for connected m-edge graphs G that are not k-cliques. The bound is attained by infinitely many (non-isomorphic) graphs. The proof of the bound depends on determining the graphs attaining the bound. This appears to be a new feature in the literature on isolation. Among the result’s consequences are a sharp bound of Fenech, Kaemawichanurat, and the present author on the k-clique isolation number and a sharp bound on the cycle isolation number.