E-resources
Peer reviewed
-
Qiao, Hongwei; Sabir, Eminjan; Meng, Jixiang
Discrete Applied Mathematics, 03/2023, Volume: 328Journal Article
Embedding cycles into a network topology is crucial for the network simulation. In particular, embedding Hamiltonian cycles is a major requirement for designing good interconnection networks. A graph G is called k-spanning cyclable if, for any k distinct vertices v1,v2,…,vk of G, there exist k cycles C1,C2,…,Ck in G such that vi is on Ci for every i, and every vertex of G is on exactly one cycle Ci. If k=1, this is the classical Hamiltonian problem. In this paper, we focus on embedding spanning disjoint cycles in Cayley graphs Γn generated by transposition trees and show that Γn is k-spanning cyclable if k≤n−2 and n≥3. Moreover, the result is optimal with respect to the degree of Γn.
