Isolation of regular graphs, stars and $k$-chromatic graphs

Abstract

Given a set $\mathcal{F}$ of graphs, we call a copy of a graph in $\mathcal{F}$ an $\mathcal{F}$-graph. The $\mathcal{F}$-isolation number of a graph $G$, denoted by $\iota (G,\mathcal{F})$, is the size of a smallest set $D$ of vertices of $G$ such that the closed neighbourhood of $D$ intersects the vertex sets of the $\mathcal{F}$-graphs contained by $G$ (equivalently, $G-N[D]$ contains no $\mathcal{F}$-graph). Thus, $\iota (G,\{K_1\})$ is the domination number of $G$. Clearly, $\iota (G,\mathcal{F})\le \iota (G,\mathcal{F}\cup \mathcal{H})$. For any integer $k\ge 1$, let ${\mathcal{F}}_{0,k}$ be the set consisting of the $k$-star $K_{1,k}$, let ${\mathcal{F}}_{1,k}$ be the set of regular graphs whose degree is at least $k-1$, let ${\mathcal{F}}_{2,k}$ be the set of graphs whose chromatic number is at least $k$, and let ${\mathcal{F}}_{3,k}$ be the union ${\mathcal{F}}_{0,k}\cup {\mathcal{F}}_{1,k}\cup {\mathcal{F}}_{2,k}$. We prove that if $G$ is a connected $n$-vertex graph, then $\iota (G,{\mathcal{F}}_{3,k})\le \frac{n}{k+1}$ unless $G$ is a $k$-clique or $k=2$ and $G$ is a $5$-cycle. This generalizes a classical bound of Ore on the domination number, a bound of Caro and Hansberg and of Żyliński on the vertex-edge domination number, a bound of Fenech, Kaemawichanurat and the author on the $k$-clique isolation number, a bound of the author on the cycle isolation number, and a bound of Caro and Hansberg on the ${\mathcal{F}}_{0,k}$-isolation number. The proof features a new strategy. For $i=1,2,3$, the bound $\frac{n}{k+1}$ on $\iota (G,{\mathcal{F}}_{i,k})$ is attainable if $k+1$ divides $n$. Our second main result is that the bound $\frac{n}{k+1}$ on $\iota (G,{\mathcal{F}}_{0,k})$ is attainable if and only if $n$ is $0$ or $k+1$ or $2(k+1)$. We pose some problems and conjectures, and establish additional intriguing phenomena concerning $k$-star isolation and $k$-cycle isolation.

16 pages, Theorem 6 has been added, minor corrections have been made

References in corpus (1)

• Graphs with isolation number equal to one third of the order