PreprintCC BY 4.0arXiv
Small and Large Quasi-Kernels in General Digraphs
Abstract
In a digraph D, a set Q of vertices is a quasi-kernel if Q is an independent set and every vertex in D can be reached from Q via at most two edges. The small quasi-kernel conjecture by Erdős and Székely predicts that every source-free n-vertex digraph contains a quasi-kernel of size at most $n - n/2$. Chvátal and Lovász' 1974 work implies a bound of n − √n+1. In 2024, Sprio shows the bound n − 1/4 √(n log2 n). We show that there always is a quasi-kernel of size at most n − 1/51n2/3 / ln2/3(n). For the related large quasi-kernel conjecture by Spiro, we show that there always is a quasi-kernel Q with |N+[Q]| ≥ 0.2917 · n2/3 / ln2/3(n).
Related
- Small and large quasi-kernels: a weighted transfer theorem
- Hamiltonicity and cycle factors in k-quasi-transitive digraphs of large diameter
- s-quasi-transitive weakly distance-regular digraphs
- The Path Partition Conjecture and 3-(quasi-)Transitive Digraphs
- Quasi-strongly regular digraphs constructed from transitive groups of degree n≤ 110
BibTeX
@misc{rutschmann2026small,
title = {{Small and Large Quasi-Kernels in General Digraphs}},
author = {Daniel Rutschmann},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29659},
eprint = {2610.29659},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29659},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Small and Large Quasi-Kernels in General Digraphs
AU - Daniel Rutschmann
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29659
UR - https://arxiv.org/abs/2610.29659
AB - In a digraph D, a set Q of vertices is a quasi-kernel if Q is an independent set and every vertex in D can be reached from Q via at most two edges. The small quasi-kernel conjecture by Erdős and Székely predicts that every source-free n-vertex digraph contains a quasi-kernel of size at most $n - n/2$. Chvátal and Lovász' 1974 work implies a bound of n − √n+1. In 2024, Sprio shows the bound n − 1/4 √(n log_2 n). We show that there always is a quasi-kernel of size at most n − 1/51n^2/3 / ln^2/3(n). For the related large quasi-kernel conjecture by Spiro, we show that there always is a quasi-kernel Q with |N^+[Q]| ≥ 0.2917 · n^2/3 / ln^2/3(n).
ER -