k‐Kings in k‐Quasitransitive Digraphs |
| |
Authors: | Ruixia Wang Wei Meng |
| |
Affiliation: | SCHOOL OF MATHEMATICAL SCIENCE OF SHANXI UNIVERSITY, TAIYUAN, P.R. CHINA |
| |
Abstract: | 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. |
| |
Keywords: | quasitransitive digraph k‐quasitransitive digraph k‐king k‐kernel |
|
|