k-Kings in k-Quasitransitive Digraphs
Let D be a digraph with vertex set and arc set . A vertex x is a k-king of D, if for every , there is an -path of length at most k. A subset N of is k-independent if for every pair of vertices , we have and ; it is l-absorbent if for every there exists such that . A -kernel of D is a k-independent and l-absorbent subset of . A k-kernel is a -kernel. A digraph D is k-quasitransitive, if for any path of length k, x0 and are adjacent. In this article, we will prove that a k-quasitransitive digraph with has a k-king if and only if it has a unique initial strong component and the unique initial strong component is not isomorphic to an extended -cycle where each has at least two vertices. Using this fact, we show that every strong k-quasitransitive digraph has a -kernel.
k-king k-quasitransitive digraph k-kernel quasitransitive digraph