Results on the small quasi-kernel conjecture

Jiangdong Ai, Stefanie Gerke, Gregory Gutin*, Anders Yeo, Yacong Zhou


Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

20 Downloads (Pure)


A quasi-kernel of a digraph D is an independent set Q⊆V(D) such that for every vertex v∈V(D)﹨Q, there exists a directed path with one or two arcs from v to a vertex u∈Q. In 1974, Chvátal and Lovász proved that every digraph has a quasi-kernel. In 1976, Erdős and Székely conjectured that every sink-free digraph D=(V(D),A(D)) has a quasi-kernel of size at most |V(D)|/2. In this paper, we give a new method to show that the conjecture holds for a generalization of anti-claw-free digraphs. For any sink-free one-way split digraph D of order n, when n≥3, we show a stronger result that D has a quasi-kernel of size at most [Formula presented], and the bound is sharp.

TidsskriftDiscrete Mathematics
Udgave nummer7
Antal sider9
StatusUdgivet - jul. 2023

Bibliografisk note

Funding Information:
Research of Anders Yeo was partially supported by grant DFF-7014-00037B of Independent Research Fund Denmark . Research of Yacong Zhou was supported by China Scholarship Council (CSC), grant number 202106890019.


Dyk ned i forskningsemnerne om 'Results on the small quasi-kernel conjecture'. Sammen danner de et unikt fingeraftryk.