Large generalized cycles

A generalized cycle is a digraph whose set of vertices is partitioned in se veral parts that are cyclically ordered in such a way that the vertices in one part are adjacent only to vertices in the next part. The problems consi dered in this paper are: 1. To find generalized cycles with given maximum out-degree and diameter th at have large order. 2. To find generalized cycles with small diameter for given values of their maximum out-degree and order. A bound is given for both problems. It is proved that the first bound can o nly be attained for small values of the diameter. We present two new famili es of generalized cycles that provide some solutions to these problems. The se families are a generalization of the generalized de Bruijn and Kautz dig raphs and the bipartite digraphs BD(d, n). (C) 1998 Elsevier Science B.V. A ll rights reserved.