Upper bounds on the $k$-isolation number

Abstract

The isolation number of a graph $G$ (also called the vertex-edge domination number of $G$), denoted by ${\hat{I}}^1(G)$, is the size of a smallest subset $D$ of the vertex set $V(G)$ of $G$ such that $G-N[D]$ (the graph obtained by deleting the closed neighbourhood $N[D]$ of $D$ from $G$) has no edges. For $k\ge 1$, the $k$-isolation number of $G$ is the size of a smallest subset $D$ of $V(G)$ such that the maximum degree of $G-N[D]$ is at most $k-1$. Thus, ${\hat{I}}_1^1(G)={\hat{I}}^1(G)$. Let $n$ and $\ell$ be the number of vertices and the number of leaves of $G$, respectively. We show that if $n\ge 3$ and $G$ is connected, then ${\hat{I}}_k^1(G)\le \frac{n-\ell }{2}$. We also show that if $G$ is a tree $T$, then ${\hat{I}}^1(T)\le \frac{n+\ell }{4}$ and ${\hat{I}}_k^1(T)\le \frac{n+\ell }{2k+1}$ for $k\ge 2$. These bounds together improve the inequality ${\hat{I}}_k^1(T)\le \frac{n}{k+2}$ of Caro and Hansberg except that their inequality is better if $k\ge 2$ and $\frac{k-1}{k+2}n<\ell <\frac{k}{k+2}n$. Each of the new bounds is attainable if it is an integer. For each of them, we characterize all the graphs that attain it.

28 pages, 12 figures