Isolation of Regular Graphs and k-Chromatic Graphs

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 - N[D]$$ G - N [ D ] contains no F F -graph). Thus, ι (G,₁\) ι ( G , { K 1 } ) is the domination number of G . For any integer k ≥ 1 k ≥ 1 , let F1,k F 1 , k be the set of regular graphs of degree at least $$k-1$$ k - 1 , let F2,k F 2 , k be the set of graphs whose chromatic number is at least k , and let F3,k F 3 , k be the union of F1,k F 1 , k and F2,k F 2 , k . Thus, k -cliques are members of both F1,k F 1 , k and F2,k F 2 , k . We prove that for each i ∈ \1, 2, 3\ i ∈ { 1 , 2 , 3 } , m+1k ()2 + 2 m + 1 k 2 + 2 is a best possible upper bound on ι (G, Fi,k) ι ( 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.