Covering the vertices of a Cycle Prefix Digraph.
F. Comellas(*), M. Mitjana(#)
(*) Departament de Matemàtica Aplicada i Telemàtica; Universitat
Politècnica de Catalunya
(#) Departament de Matemàtica Aplicada I; Universitat Politècnica
de Catalunya
Proceedings I Jornades de Matemàtica Discreta i Algorísmica.
pp. 20-23 (Barcelona, 23-24 març 1998), DL B-15.873-98.
Cycle prefix digraphs are an interesting family of directed Cayley
coset graphs that have been proposed as a model of interconnection networks
for parallel architectures. They have many remarkable communication
properties such as symmetry, large number of nodes for a given degree and
diameter, simple shortest path routing, Hamiltonicity, optimal connectivity,
etc. The digraphs can be decomposed into vertex--disjoint cycles of the
same length as it was shown in \cite{CoMi97}. However, the distribution
of tasks of different size in a network should be based in a decomposition
of the digraph in
vertex--disjoint paths of different length. In this paper we
show that the cycle prefix digraph $\Gamma_{\Delta}(D)$ can
be decomposed into one single path with $(D+1)!$ vertices and ${\Delta-D+k}
\choose {k+1}$ paths of $(D-k)D!$ vertices, for $k=0 \dots D$.
Load a preprint version of the paper: