论文标题
$ k $ - quasi transitive digraphs具有大直径的结构
The structure of strong $k$-quasi-transitive digraphs with large diameters
论文作者
论文摘要
让$ k $为$ k \ geq 2 $的整数。 Digraph $ d $是$ k $ -quasi传递，如果对于任何路径$ x_0x_1 \ ldots x_k $ length $ k $，$ x_0 $，$ x_0 $和$ x_k $是相邻的。假设存在一条长度至少$ k+2 $ in $ d $中的路径。让$ p $是$ d $中的最短$ k+2 $的最短路径。王和张[$ k $ -quasi transitive digraphs，离散数学，339（8）（2016）2094--2099]证明，如果$ k $均匀而$ k \ ge 4 $，则$ k \ ge 4 $，则$ d [v（p）$和$ d [v（d）$ negrece， In this paper, we shall prove that if $k$ is odd and $k\ge 5$, then $D[V(P)]$ is either a semicomplete digraph or a semicomplete bipartite digraph and $D[V(D)\setminus V(P)]$ is either a semicomplete digraph, a semicomplete bipartite digraph or an empty digraph.
Let $k$ be an integer with $k\geq 2$. A digraph $D$ is $k$-quasi-transitive, if for any path $x_0x_1\ldots x_k$ of length $k$, $x_0$ and $x_k$ are adjacent. Suppose that there exists a path of length at least $k+2$ in $D$. Let $P$ be a shortest path of length $k+2$ in $D$. Wang and Zhang [Hamiltonian paths in $k$-quasi-transitive digraphs, Discrete Mathematics, 339(8) (2016) 2094--2099] proved that if $k$ is even and $k\ge 4$, then $D[V(P)]$ and $D[V(D)\setminus V(P)]$ are both semicomplete digraphs. In this paper, we shall prove that if $k$ is odd and $k\ge 5$, then $D[V(P)]$ is either a semicomplete digraph or a semicomplete bipartite digraph and $D[V(D)\setminus V(P)]$ is either a semicomplete digraph, a semicomplete bipartite digraph or an empty digraph.
