Cycle Embedding in Generalized Recursive Circulant Graphs

Shyue-Ming TANG  Yue-Li WANG  Chien-Yi LI  Jou-Ming CHANG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E101-D   No.12   pp.2916-2921
Publication Date: 2018/12/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018PAP0009
Type of Manuscript: Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking)
Category: Graph Algorithms
Keyword: 
interconnection networks,  generalized recursive circulant graphs,  recursive circulant graphs,  cycle embedding,  pancyclicity,  bipancyclicity,  

Full Text: PDF(650.5KB)
>>Buy this Article


Summary: 
Generalized recursive circulant graphs (GRCGs for short) are a generalization of recursive circulant graphs and provide a new type of topology for interconnection networks. A graph of n vertices is said to be s-pancyclic for some $3leqslant sleqslant n$ if it contains cycles of every length t for $sleqslant tleqslant n$. The pancyclicity of recursive circulant graphs was investigated by Araki and Shibata (Inf. Process. Lett. vol.81, no.4, pp.187-190, 2002). In this paper, we are concerned with the s-pancyclicity of GRCGs.