The Large Quasikernel Conjecture

Let DD be a finite digraph. A quasikernel is an independent set QV(D)Q\subseteq V(D) such that every vertex xV(D)x\in V(D) satisfies dist(Q,x)2\operatorname{dist}(Q,x)\le 2. For SV(D)S\subseteq V(D), its closed out-neighborhood is

N+[S]=S{v:uS, uvE(D)}.N^+[S]=S\cup\{v:\exists u\in S,\ uv\in E(D)\}.

Large Quasikernel Conjecture. Every digraph DD contains a quasikernel QQ with

N+[Q]12V(D).|N^+[Q]|\ge\frac{1}{2}|V(D)|.

This is a weak form of the Small Quasikernel Conjecture in terms of the portion of the digraph covered directly by a quasikernel. The source reports partial progress but no resolution.

Sources & referencesView supporting material

Primary source

Sam Spiro, “Generalized Quasikernels in Digraphs”, arXiv:2404.07305 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.