For any graph $G$ and any set $\mathcal{F}$ of graphs, let $\iota(G,\mathcal{F})$ 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 $\mathcal{F}$. Thus, $\iota(G,\{K_1\})$ is the domination number of $G$. For any integer $k \geq 1$, let $\mathcal{F}_{0,k} = \{K_{1,k}\}$, let $\mathcal{F}_{1,k}$ be the set of regular graphs of degree 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 of $\mathcal{F}_{0,k}$, $\mathcal{F}_{1,k}$ and $\mathcal{F}_{2,k}$. We prove that if $G$ is a connected $n$-vertex graph and $\mathcal{F} = \mathcal{F}_{0,k} \cup \mathcal{F}_{1,k}$, then $\iota(G, \mathcal{F}) \leq \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 on the $\{K_{1,k}\}$-isolation number, a bound of the author on the cycle isolation number, and a bound of Fenech, Kaemawichanurat and the author on the $k$-clique isolation number. By Brooks' Theorem, the same holds if $\mathcal{F} = \mathcal{F}_{3,k}$. The bounds are sharp.
翻译:对于任意图$G$和任意图集$\mathcal{F}$,令$\iota(G,\mathcal{F})$表示在$G$中删除$\mathcal{F}$中某些图的所有子图所需的最小顶点集合$D$的大小。因此,$\iota(G,\{K_1\})$是$G$的支配数。对于任意整数$k\geq 1$,令$\mathcal{F}_{0,k}=\{K_{1,k}\}$,$\mathcal{F}_{1,k}$为度不低于$k-1$的正则图集合,$\mathcal{F}_{2,k}$为色数不低于$k$的图集合,$\mathcal{F}_{3,k}$为$\mathcal{F}_{0,k}$、$\mathcal{F}_{1,k}$和$\mathcal{F}_{2,k}$的并集。我们证明,如果$G$是$ n $个顶点的连通图,$\mathcal{F}= \mathcal{F}_{0,k} \cup \mathcal{F}_{1,k}$,则$\iota(G, \mathcal{F})\leq \frac{n}{k+1}$,除非$G$是$k$-团或$k=2$且$G$是$5$-环。这推广了Ore关于支配数的经典界限,Caro和Hansberg关于$\{K_{1,k}\}$-孤立数的界限,作者关于环孤立数的界限,以及Fenech、Kaemawichanurat和作者关于$k$-团孤立数的界限。根据Brooks定理,如果$\mathcal{F}= \mathcal{F}_{3,k}$,则同样成立。这些界限是最优的。