On the existence and number of $(k+1)$-kings in $k$-quasi-transitive digraphs

Abstract

Let $D=(V(D),A(D))$ be a digraph and $k\ge 2$ an integer. We say that $D$ is $k$-quasi-transitive if for every directed path $(v_0,v_1,...,v_k)$ in $D$, then $(v_0,v_k)\in A(D)$ or $(v_k,v_0)\in A(D)$. Clearly, a 2-quasi-transitive digraph is a quasi-transitive digraph in the usual sense. Bang-Jensen and Gutin proved that a quasi-transitive digraph $D$ has a 3-king if and only if $D$ has a unique initial strong component and, if $D$ has a 3-king and the unique initial strong component of $D$ has at least three vertices, then $D$ has at least three 3-kings. In this paper we prove the following generalization: A $k$-quasi-transitive digraph $D$ has a $(k+1)$-king if and only if $D$ has a unique initial strong component, and if $D$ has a $(k+1)$-king then, either all the vertices of the unique initial strong components are $(k+1)$-kings or the number of $(k+1)$-kings in $D$ is at least $(k+2)$.

arXiv comment17 pages

Cited by in corpus (1)

• The structure of strong $k$-quasi-transitive digraphs with large diameters