Small $q$-kernels in digraphs with minimum in-degree $\hat{I}´$

Abstract

For a digraph $D$, a subset $Q\subseteq V(D)$ is called a $q$-kernel if $Q$ is an independent set and all vertices in $V(D)$ are reachable from $Q$ via a directed path of length at most $q$. Given integers $q\ge 2$ and $\hat{I}´\ge 1$, Spiro arXiv:2404.07305 [math.CO] posed the question: what is the smallest constant $c_{\hat{I}´,q}$ such that every digraph $D$ with minimum in-degree $\hat{I}´$ has a $q$-kernel of size at most $c_{\hat{I}´,q}|V(D)|$? We show the constants $c_{\hat{I}´,q}$ are monotone in both $\hat{I}´$ and $q$, and we improve upon the known upper bounds for $c_{\hat{I}´,q}$. Our main results show $\frac{1}{\hat{I}´+1}\le c_{\hat{I}´,q}\le \frac{1}{\lfloor \sqrt{\hat{I}´+1}\rfloor +1}$ for all $q\ge 3$ and $\hat{I}´\ge 1$, and $c_{\hat{I}´,q}=\frac{1}{\hat{I}´+1}$ whenever $\hat{I}´\ge 1$ and $q\ge \lceil \frac{3\hat{I}´}{2}\rceil +1$.

15 pages, 2 figures