Kernels in digraphs with covering number at most 3

DOI10.1016/S0012-365X(02)00375-8MaRDI QIDQ1861206zbMATH OpenOpenAlexFDO

Authors Hortensia Galeana-Sánchez

Publication date 16 March 2003

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(02)00375-8

zbMATH Keywords

covering numberkernelkernel-perfect digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Review text

A digraph \(D\) is said to be kernel-perfect if every proper induced subdigraph of \(D\) possesses a kernel. In 1998, the author (with her coauthor Xuliang Li) published two sufficient conditions for a digraph \(D\) to be kernel-perfect, concerning digraphs with the covering number at most three, containing only symmetrical directed triangles. In this paper the class of \(M\)-oriented digraphs is considered and a common generalization of both previous conditions is presented. The main result is the following one: Let every directed triangle of a digraph \(D\) have at least two symmetrical arcs. If each directed cycle of length five in \(D\) has two diagonals or three symmetrical arcs, then \(D\) is kernel-perfect.

Recommendations

• On the existence of 3- and 4-kernels in digraphs
• On the complexity of the 3-kernel problem in some classes of digraphs
• Kernels in a special class of digraphs
• scientific article; zbMATH DE number 1275896
• Kernels by monochromatic paths in digraphs with covering number 2
• Kernels in circulant digraphs
• A sufficient condition for the existence of k-kernels in digraphs
• Kernels in planar digraphs
• On the existence of (k,\(\ell)\)-kernels in digraphs
• A note on kernels and solutions in digraphs

Cited in

(9)

• Absorbant of generalized de Bruijn digraphs
• KP-digraphs and CKI-digraphs satisfying the k-Meyniel's condition
• Kernel perfect and critical kernel imperfect digraphs structure
• A sufficient condition for a digraph to be kernel-perfect
• Characterization of asymmetric CKI- and KP-digraphs with covering number at most 3
• At least three minimal quasi-kernels
• Some sufficient conditions on odd directed cycles of bounded length for the existence of a kernel
• On claw-freeM-oriented critical kernel-imperfect digraphs
• Kernels by monochromatic paths in digraphs with covering number 2

This page was built for publication: Kernels in digraphs with covering number at most 3

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