The minimum in-degree conjecture for small quasikernels
The minimum in-degree conjecture for small quasikernels
Let be a finite digraph. A quasikernel is an independent set such that every vertex is reachable from by a directed path of length at most . The minimum in-degree of is denoted by .
Minimum in-degree quasikernel conjecture. There exists an integer such that every digraph with contains a quasikernel with
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.