Isolation of regular graphs and k-chromatic graphs
share
For any set ℱ of graphs and any graph G, let ι(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 does not contain a copy of a graph in ℱ. Thus, ι(G,{K_1}) is the domination number of G. For any integer k ≥ 1, let ℱ_1,k be the set of regular graphs of degree at least k-1, let ℱ_2,k be the set of graphs whose chromatic number is at least k, and let ℱ_3,k be the union of ℱ_1,k and ℱ_2,k. We prove that for each i ∈{1, 2, 3}, if G is a connected m-edge graph that is not a k-clique, then ι(G, ℱ_i,k) ≤m+1/k 2 + 2. We also determine the graphs for which the bound is attained. Among the 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.
READ FULL TEXT