Small quasi-kernels in directed graphs

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $D=(V,A)$ be a finite loopless digraph with $n=|V|$ and $d^+(v)\ge1$ for every vertex. Here a quasi-kernel is an independent set $Q\subseteq V$ such that every vertex $v$ has a directed path of length at most two from $v$ to some $q\in Q$. Independence means there is no arc in either direction between two members of $Q$. Length-zero paths are allowed; thus vertices in $Q$ satisfy the condition themselves. This is the inward convention used with the positive-outdegree hypothesis.

Statement recorded in the supplied source.

Does every such sink-free digraph have a quasi-kernel $Q$ with $|Q|\le n/2$? [S2]

Short English statement

Does every finite directed graph without sinks have an independent set of at most half its vertices reachable from every vertex within two steps?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3000079 (AMR-029-0079). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 H. Langlois, F. Meunier, R. Rizzi, S. Vialette and Y. Zhou, Quasi-kernels in split graphs (2024), Introduction, quasi-kernel definition and Conjecture 1, p.1. https://arxiv.org/pdf/2312.15519.