Isolation of Regular Graphs and k-Chromatic Graphs
Peter Borg · Mediterranean Journal of Mathematics · 2024
Abstract Given a set $${\mathcal {F}}$$ F of graphs, we call a copy of a graph in $${\mathcal {F}}$$ F an $${\mathcal {F}}$$ F -graph. The $${\mathcal {F}}$$ F -isolation number of a graph G , denoted by $$\iota (G,{\mathcal {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 $${\mathcal {F}}$$ F -graphs contained by G (equivalently, $$G - N[D]$$ G - N [ D ] contains no $${\mathcal {F}}$$ F -graph). Thus, $$\iota (G,\{K_1\})$$ ι ( G , { K 1 } ) is the domination number of G . For any integer $$k \ge 1$$ k ≥ 1 , let $${\mathcal {F}}_{1,k}$$ F 1 , k be the set of regular graphs of degree at least $$k-1$$ k - 1 , let $${\mathcal {F}}_{2,k}$$ F 2 , k be the set of graphs whose chromatic number is at least k , and let $${\mathcal {F}}_{3,k}$$ F 3 , k be the union of $${\mathcal {F}}_{1,k}$$