A generalized cycle is a digraph whose set of vertices is partitioned in several 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 considered in this paper are: 1. To find generalized cycles with given maximum out-degree and diameter that 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 only be attained for small values of the diameter. We present two new families of generalized cycles that provide some solutions to these problems. These families are a generalization of the generalized de Bruijn and Kautz digraphs and the bipartite digraphs BD(d, n). (C) 1998 Elsevier Science B.V. All rights reserved. [References: 14]
展开▼
