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

Let D=(V(D),A(D))D=(V(D),A(D)) be a digraph and k≥2k≥2 an integer. We say that DD is kk-quasi-transitive if for every directed path (v0,v1,…,vk)(v0,v1,…,vk) in DD we have (v0,vk)∈A(D)(v0,vk)∈A(D) or (vk,v0)∈A(D)(vk,v0)∈A(D). Clearly, a 22-quasi-transitive digraph is a quasi-transitive digraph in the usual sense.Bang-Jensen and Gutin proved that a quasi-transitive digraph DD has a 33-king if and only if DD has a unique initial strong component, and if DD has a 33-king and the unique initial strong component of DD has at least three vertices, then DD has at least three 33-kings. In this paper we prove the following generalization: a kk-quasi-transitive digraph DD has a (k+1)(k+1)-king if and only if DD has a unique initial strong component, and if DD has a (k+1)(k+1)-king, then either all the vertices of the unique initial strong components are (k+1)(k+1)-kings or the number of (k+1)(k+1)-kings in DD is at least (k+2)(k+2). Also, we obtain new results on the minimum number of 33-kings in quasi-transitive digraphs.