## Abstract

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.

Originalsprog | Engelsk |
---|---|

Artikelnummer | 113435 |

Tidsskrift | Discrete Mathematics |

Vol/bind | 346 |

Udgave nummer | 7 |

Antal sider | 9 |

ISSN | 0012-365X |

DOI | |

Status | Udgivet - 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.