{"id":"arxiv/2611.22881","url":"https://arxiv.org/abs/2611.22881","tags":["math.CO"],"score":0,"title":"Equivalence of Small and Large Quasi-kernels","domain":"math.CO","source":"arxiv","authors":["Sam Spiro"],"reviews":0,"subject":"math.CO","summary":"A quasi-kernel of a digraph $D$ is an independent set which can reach every vertex of $D$ by a directed path of length at most 2. The Small Quasi-kernel Conjecture states that every $n$-vertex source-free digraph $D$ contains a quasi-kernel $Q$ with $|Q|\\le n/2$, and the Large Quasi-kernel Conjecture states that every $n$-vertex digraph $D$ contains a quasi-kernel $Q$ with $|N^+[Q]|\\ge n/2$. Our main result shows for any $\\frac{1}{2}<β<1$ an equivalence between the following two statements: \\[\\textrm{Every }n\\textrm{-vertex source-free digraph contains a quasi-kernel with } |Q|\\le…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-17","reactions":{}}