✦ LIBER ✦
Characterizations of vertex pancyclic and pancyclic ordinary complete multipartite digraphs
✍ Scribed by G. Gutin
- Publisher
- Elsevier Science
- Year
- 1995
- Tongue
- English
- Weight
- 527 KB
- Volume
- 141
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
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 XwY coincides with X x Y=l(x,y): x~X, yeY I or Y x X or X x Yu Y x X. We characterize all the pancyclic and vertex pancyclic ordinary complete multipartite graphs. Our charcterizations admit polynomial time algorithms.