Small and large quasi-kernels: a weighted transfer theorem
A quasi-kernel of a digraph $D$ is an independent set from which every vertex is reachable by a directed path of length at most two. The Small Quasi-kernel Conjecture asserts that every source-free digraph on $n$ vertices has a quasi-kernel of size at most $n/2$, whereas the Large Quasi-kernel Conjecture asks for a quasi-kernel whose closed out-neighbourhood has size at least $n/2$. Spiro proved that the former implies the latter. In this paper, we establish a weighted transfer theorem: if every nonnegative integer weighting of a source-free digraph $D$ admits a quasi-kernel whose closed…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.23487
curl -X POST /api/v1/records/arxiv/2610.23487/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.23487/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'