The Structure Of Strong K-quasi-transitive Digraphs

A digraph D is a k-quasi-transitive digraph,if for a path x0x1…xk of length k in D,x0 and xk are adjacent.A 2-quasi-transitive digraph is called a quasi-transitive digraph.The concept of k-quasi-transitive was introduced as a generalization of quasi-transitive digraphs by Galeana-Sanchez et al.Quasi-transitive digraphs and k-quasi-transitive digraphs are important class of digraphs.In recent years,a large number of researchers have paid attention to the structural characterization and other related field of the family of digraphs,and there are some nice results in this direction.The aim of this article is to characterize strong k-quasi-transitive digraphs with diam(D)?k + 2.The thesis consists of three sections.In Chapter 1,we introduce the research background,development of k-quasi-transitive digraphs and some basic concepts related to this paper.In Chapter 2,we study the structure of strong k-quasi-transitive digraphs with even k and diam(D)? k + 2.Suppose that P is a shortest path of length k + 2 in D,we get the following results:(1)D[V(P)]and D[V(D)\V(C)]are both semicomplete digraphs.(2)D has a Hamiltonian path.In Chapter 3,we study the structure of strong k-quasi-transitive digraphs with odd k and diam(D)>? k 2.Suppose that P is a shortest path of length k + 2 in D,we get the following results:(1)D[V(P)]is either a semicomplete bipartite digraph or a semicomplete digraph.(2)Let Bc = {x? V(D)\V(P):(x,V(P))?(?)and(V(P),x)?(?)},then D[BC]is either a semicomplete bipartite digraph or a semicomplete digraph or an empty digraph.