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\geq 2$ and $\delta\geq 1$, Spiro arXiv:2404.07305 [math.CO] posed the question: what is the smallest constant $c_{\delta,q}$ such that every digraph $D$ with minimum in-degree $\delta$ has a $q$-kernel of size at most $c_{\delta,q}|V(D)|$? We show the constants $c_{\delta,q}$ are monotone in both $\delta$ and $q$, and we improve upon the known upper bounds for $c_{\delta,q}$. Our main results show $\frac{1}{\delta+1} \leq c_{\delta,q}\leq \frac{1}{\lfloor\sqrt{\delta+1}\rfloor+1}$ for all $q \geq 3$ and $\delta \geq 1$, and $ c_{\delta,q}=\frac{1}{\delta+1}$ whenever $\delta \geq 1$ and $q \geq \left\lceil\frac{3\delta}{2}\right\rceil + 1$.
From: Isaiah Hollars [view email]
[v1]
Mon, 15 Jun 2026 17:08:44 UTC (131 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。