Results on the small quasi-kernel conjecture

DOI10.1016/J.DISC.2023.113435MaRDI QIDQ6041861zbMATH OpenOpenAlexWikidataFDO

Authors Jiangdong Ai, Stefanie Gerke, G. Gutin, A. Yeo, Y. C. Zhou

Publication date 15 May 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2207.12157

zbMATH Keywords

directed graphkernelquasi-kernel

Mathematics Subject Classification ID

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

Abstract: A {em quasi-kernel} of a digraph $D$ is an independent set $QsubseteqV(D)$ such that for every vertex $$, there exists a directed path with one or two arcs from $v$ to a vertex $uinQ$. In 1974, Chv'{a}tal and Lov'{a}sz proved that every digraph has a quasi-kernel. In 1976, ErdH{o}s and S'zekely 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 $ngeq3$, we show a stronger result that $D$ has a quasi-kernel of size at most $fracn+32-sqrtn$, and the bound is sharp.

Recommendations

• Towards the small quasi-kernel conjecture
• On the number of quasi-kernels in digraphs
• Disjoint quasi-kernels in digraphs
• A note on quasi-kernels in digraphs
• Quasi-kernels and quasi-sinks in infinite graphs

Cites work

• A note on quasi-kernels in digraphs
• About quasi-kernels in a digraph
• Algorithmic aspects of small quasi-kernels
• Classes of directed graphs
• Claw-free graphs---a survey
• Digraphs
• Disjoint quasi-kernels in digraphs
• scientific article; zbMATH DE number 3465337 (Why is no real title available?)
• On the number of quasi-kernels in digraphs
• Solutions of irreflexive relations
• Split digraphs
• The structure of claw-free graphs
• Threshold graphs and related topics
• Towards the small quasi-kernel conjecture
• Zero-one matrices with zero trace

Cited in

(9)

• Towards the small quasi-kernel conjecture
• At least three minimal quasi-kernels
• Strong arc decompositions of split digraphs
• Quasi-kernels in split graphs
• Distant digraph domination
• Generalized quasikernels in digraphs
• A variable version of the quasi-kernel conjecture
• On the small quasi-kernel conjecture -- a survey
• Counterexamples to a problem of spiro on k-kernels

This page was built for publication: Results 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 Q6041861)