×

A sufficient condition for the existence of \(k\)-kernels in digraphs. (English) Zbl 0928.05032

Let \(k\) \((\geq 2)\) be a fixed integer. Let \(D\) be a digraph with the following properties: (i) the spanning subdigraph determined by the asymmetrical arcs of \(D\) is strongly connected; (ii) every directed 3-cycle of \(D\) has at least two symmetrical arcs; (iii) if \(C\) is a directed cycle whose length is not a multiple of \(k\) then either \(C\) has two symmetrical arcs or \(D\) contains four chords of \(C\) of the form \((u,v)\) where \(v\) is the successor of the successor of \(u\) in \(C\). The authors show that such a digraph \(D\) contains a \(k\)-kernel.

MSC:

05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI