Generalized Quasikernels in Digraphs

Given a digraph $D$, we say that a set of vertices $Q\subseteq V(D)$ is a $q$-kernel if $Q$ is an independent set and if every vertex of $D$ can be reached from $Q$ by a path of length at most $q$. In this paper, we initiate the study of several extremal problems for $q$-kernels. For example, we introduce and make progress on (what turns out to be) a weak version of the Small Quasikernel Conjecture, namely that every digraph contains a $q$-kernel with $\mathrm{\mid }{N}^{+}[Q]\mathrm{\mid }\ge \frac{1}{2}\mathrm{\mid }V(D)\mathrm{\mid }$ for all $q\ge 2$.