{"id":"arxiv/2606.16971","url":"https://arxiv.org/abs/2606.16971","tags":["math.CO"],"score":0,"title":"Small $q$-kernels in digraphs with minimum in-degree $δ$","domain":"math.CO","source":"arxiv","authors":["Geoffrey Boyer","Matt Burnham","Daniela Černá","Stephen G. Hartke","Isaiah Hollars","Joel Jeffries","Sydney Miyasaki","Tobias Timofeyev"],"reviews":0,"subject":"math.CO","summary":"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\\geq 2$ and $δ\\geq 1$, Spiro arXiv:2404.07305 [math.CO] posed the question: what is the smallest constant $c_{δ,q}$ such that every digraph $D$ with minimum in-degree $δ$ has a $q$-kernel of size at most $c_{δ,q}|V(D)|$? We show the constants $c_{δ,q}$ are monotone in both $δ$ and $q$, and we improve upon the known upper bounds for $c_{δ,q}$. Our main results show $\\frac{1}{δ+1} \\leq…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-15","reactions":{}}