Characterizations of vertex pancyclic and pancyclic ordinary complete multipartite digraphs

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 vert...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 1995-06, Vol.141 (1), p.153-162
Main Author: Gutin, G.
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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): xϵX, yϵY} 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.
ISSN:0012-365X
1872-681X
DOI:10.1016/0012-365X(93)E0195-A