Characterizations of vertex pancyclic and pancyclic ordinary semicomplete multipartite digraphs

Abstract

A digraph obtained by replacing each edge of a complete multipartite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called a complete multipartite graph. Such a digraph D is called ordinary if for any pair X, Y of its partite sets the set of arcs with both end vertices in X Y coincides with X × Y = {(x, y): xX, yY} or Y × X or X × Y Y × X. We characterize all the pancyclic and vertex pancyclic ordinary complete multipartite graphs. Our charcterizations admit polynomial time algorithms.