Characterization of vertex pancyclic and pancyclic ordinary complete multipartite digraphs (Q1894766): Difference between revisions

A digraph is semicomplete if it has no pair of non-adjacent vertices. A semicomplete multipartite digraph is a digraph that can be obtained from some semicomplete digraph \(D\) by choosing a (vertex) spanning collection of vertex disjoint induced subgraphs of \(D\) and deleting all arcs inside each of these. A semicomplete multipartite digraph is called ordinary if, whenever \(x\) and \(y\) are non-adjacent vertices they have exactly the same in- and out-neighbours. Such digraphs are also called extended semicomplete digraphs since the digraph obtained by shrinking each independent set of vertices to one vertex is a semicomplete digraph. Equivalently: every ordinary semicomplete multipartite digraph \(D\) can be obtained from some semicomplete digraph \(S\) by replacing each vertex \(x\) of \(S\) by an independent set of vertices \(I_x\) and adding all possible arcs from \(I_x\) to \(I_y\) if \(x\to y\) is an arc of \(S\). In this paper, the author gives a complete characterization of pancyclic and vertex pancyclic ordinary semicomplete multipartite digraphs. These characterizations which are non-trivial lead to polynomial algorithms. Note that the author uses the term complete multipartite digraph instead of semicomplete multipartite digraph. However the last term should be preferred (and is so today, I think) because the phrase complete digraph sometimes means a digraph in which each pair of vertices induces a 2-cycle. A digraph is quasi-transitive if whenever \(x\to y\) and \(y\to z\) are arcs where \(x\), \(y\), \(z\) are distinct there is an arc between \(x\) and \(z\) (note that the arc may go in any direction, or there could be one in each direction). In [the reviewer and \textit{J. Huang}, Quasi-transitive digraphs, J. Graph Theory 20, No. 2, 141-161 (1995; Zbl 0832.05048)] Gutin's characterizations of pancyclic and vertex pancyclic ordinary semicomplete multipartite digraphs were used to characterize pancyclic and vertex pancyclic quasi-transitive digraphs. Note that an ordinary semicomplete multipartite digraph \(D\) is a quasi-transitive digraph if and only if \(D\) has no two distinct independent sets \(A\) and \(B\) such that \(|A\cup B|\geq 3\) and \(a\) and \(b\) induce a 2-cycle for every choice of vertices \(a\in A\) and \(b\in B\).