Isolation of Regular Graphs and k-Chromatic Graphs

Abstract Given a set {F} F of graphs, we call a copy of a graph in {F} F an {F} F -graph. The {F} F -isolation number of a graph G, denoted by (G, {F}) ι (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} F -graphs contained by G (equivalently, G - ND G - N D contains no {F} F -graph). Thus, (G, \K₁\) ι (G, K 1) is the domination number of G. For any integer k 1 k ≥ 1, let {F}₁, ₊ F 1, k be the set of regular graphs of degree at least k-1 k - 1, let {F}₂, ₊ F 2, k be the set of graphs whose chromatic number is at least k, and let {F}₃, ₊ F 3, k be the union of {F}₁, ₊ F 1, k and {F}₂, ₊ F 2, k. Thus, k -cliques are members of both {F}₁, ₊ F 1, k and {F}₂, ₊ F 2, k. We prove that for each i \1, 2, 3\ i ∈ 1, 2, 3, m+1{k () 2 + 2} m + 1 k 2 + 2 is a best possible upper bound on (G, {F}₈, ₊) ι (G, F i, 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.