On the Small Quasi-kernel conjecture

MaRDI QIDQ6443064zbMATH OpenFDO

Authors Péter L. Erdős, Ervin Győri, Tamás Róbert Mezei, Nika Salia, Mykhaylo Tyomkyn

Publication date 9 July 2023

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: The Chv'atal-Lov'asz theorem from 1974 establishes in every finite digraph $G$ the existence of a quasi-kernel, i.e., an independent $2$-out-dominating vertex set. In the same spirit, the Small Quasi-kernel Conjecture, proposed by ErdH{o}s and Sz'ekely in 1976, asserts the existence of a quasi-kernel of order at most $|V(G)|/2$ if $G$ does not have sources. Despite repeated efforts, the conjecture remains wide open. This work contains a number of new results towards the conjecture. In our main contribution we resolve the conjecture for all directed graphs without sources containing a kernel in the second out-neighborhood of a quasi-kernel. Furthermore, we provide a novel strongly connected example demonstrating the asymptotic sharpness of the conjecture. Additionally, we resolve the conjecture in a strong form for all directed unicyclic graphs.

This page was built for publication: On the Small Quasi-kernel conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6443064)