quasikernel

N/A

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 $|N^+[Q]|\ge \frac{1}{2}|V(D)|$ for all $q\ge 2$.

saved by

• Luke Hawranick

related reading

• balogh containersarxiv.org
• 2-reachable subsets in two-colored graphsarxiv.org
• Exact Stability for Turan's Theoremarxiv.org
• piercing intervals - gyarfasarxiv.org
• nullstellensatzweb.math.princeton.edu
• 02_GyarfasLehel_AHellyTypeProblemInTrees.pdfusers.renyi.hu
• [2604.06521] The Exact Saturation Number for the Diamondarxiv.org
• [2604.27639] How large part of a graph can be covered by the neighborhoods of k vertices?arxiv.org
• rainbow treesarxiv.org
• parity edge coloringmilans.us
• Cover times - spectralarxiv.org
• refining bounds - cover timesarxiv.org