The minimum in-degree conjecture for small quasikernels

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 is reachable from QQ by a directed path of length at most 22. The minimum in-degree of DD is denoted by δ−(D)\delta^-(D).

Minimum in-degree quasikernel conjecture. There exists an integer δ≥2\delta\ge 2 such that every digraph DD with δ−(D)≥δ\delta^-(D)\ge\delta contains a quasikernel QQ with

∣Q∣≤13∣V(D)∣.|Q|\le\frac{1}{3}|V(D)|.

This conjecture proposes that sufficiently large minimum in-degree forces a quasikernel substantially smaller than the general one-half bound. The source states that the behavior for general minimum in-degree remains unclear.

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.