×

On the cycle structure of star graphs. (English) Zbl 0801.05044

Summary: The star graph is an attractive alternative to the popular hypercube for interconnecting processors on a parallel computer. A scheme was recently proposed which decomposes an \(n\)-star into vertex disjoint cycles. In this paper, we further study the cycle structure of the star graph. This includes characterizing the cycles obtained from the decomposition and investigating the relationships among these cycles. In addition, we show that meshes and tori of certain dimensions can be embedded into the star graph with various dilations.

MSC:

05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C45 Eulerian and Hamiltonian graphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite