Qiu, Ke; Meijer, Henk; Akl, Selim G. On the cycle structure of star graphs. (English) Zbl 0801.05044 Congr. Numerantium 96, 123-141 (1993). 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. Cited in 1 Document 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.) Keywords:Hamiltonian cycle; mesh; torus; embedding; parallel computation; star graph; hypercube; cycles; cycle structure; decomposition PDFBibTeX XMLCite \textit{K. Qiu} et al., Congr. Numerantium 96, 123--141 (1993; Zbl 0801.05044)