Axiom for the small quasi-kernel conjecture

About 4 years old · traced to

Let DD be a non-empty digraph. For a vertex u∈V(D)u\in V(D), let d+(u)d^+(u) denote its out-degree, let N+[u]N^+[u] denote its closed out-neighborhood, and call a vertex a source if it has in-degree zero. Axiom for the small quasi-kernel conjecture. There exists a vertex u∈V(D)u\in V(D) such that d+(u)>0d^+(u)>0 and D−N+[u]D-N^+[u] has at most d+(u)d^+(u) sources not present in DD. If this axiom holds for every directed graph, the paper's preceding argument proves the small quasi-kernel conjecture, namely that every source-free directed graph has a quasi-kernel of size at most half its vertices.

References

Primary source

Allan van Hulst, “A Result on the Small Quasi-Kernel Conjecture”, arXiv:2212.12764 (2022).

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.