On the Small Quasi-kernel conjecture

arXiv2307.04112MaRDI QIDQ6443064FDOQ6443064

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

Publication date: 9 July 2023

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.

Mathematics Subject Classification ID

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

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)