Abstract
Let be a digraph and an integer. We say that is -quasi-transitive if for every directed path in , then or . 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 has a 3-king if and only if has a unique initial strong component and, if has a 3-king and the unique initial strong component of has at least three vertices, then has at least three 3-kings. In this paper we prove the following generalization: A -quasi-transitive digraph has a -king if and only if has a unique initial strong component, and if has a -king then, either all the vertices of the unique initial strong components are -kings or the number of -kings in is at least .
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.