The Large Quasikernel Conjecture

About 2 years old · traced to

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

N+[S]=S∪{v:∃u∈S, uv∈E(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]∣≥12∣V(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.

References

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.