The minimum in-degree conjecture for small quasikernels

Let DD be a finite digraph. A quasikernel is an independent set QV(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

Q13V(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.

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.