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 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})$为这样一个最小的点集 $D$ 的大小,使得从 $G$ 中删去 $D$ 的闭邻域所得到的图中不包含一个 $ \mathcal{F}$ 中的图的副本。因此,$\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$-环。这推广了Caro和Hansberg对 $\{K_{1,k}\}$-独立数的界限,作者对环割去数的界限和Fenech、Kaemawichanurat以及作者对 $k$-团隔离数的界限。由于Brooks定理的存在,若 $\mathcal{F} = \mathcal{F}_{3,k}$,那么相同的情况仍然成立。这些界限是尖锐的。