Complete Cycle Embedding in Crossed Cubes with Two-Disjoint-Cycle-Cover Pancyclicity

Tzu-Liang KUNG  Hon-Chan CHEN  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E98-A   No.12   pp.2670-2676
Publication Date: 2015/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E98.A.2670
Type of Manuscript: PAPER
Category: Graphs and Networks
Keyword: 
pancyclic,  vertex-disjoint cycles,  disjoint-cycle cover,  cycle embedding,  crossed cube,  

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




Summary: 
A graph G is two-disjoint-cycle-cover r-pancyclic if for any integer l satisfying rl|V(G)|-r, there exist two vertex-disjoint cycles C1 and C2 in G such that the lengths of C1 and C2 are |V(G)|-l and l, respectively, where |V(G)| denotes the total number of vertices in G. In particular, the graph G is two-disjoint-cycle-cover vertex r-pancyclic if for any two distinct vertices u and v of G, there exist two vertex-disjoint cycles C1 and C2 in G such that (i) C1 contains u, (ii) C2 contains v, and (iii) the lengths of C1 and C2 are |V(G)|-l and l, respectively, for any integer l satisfying rl|V(G)|-r. Moreover, G is two-disjoint-cycle-cover edge r-pancyclic if for any two vertex-disjoint edges (u,v) and (x,y) of G, there exist two vertex-disjoint cycles C1 and C2 in G such that (i) C1 contains (u,v), (ii) C2 contains (x,y), and (iii) the lengths of C1 and C2 are |V(G)|-l and l, respectively, for any integer l satisfying rl|V(G)|-r. In this paper, we first give Dirac-type sufficient conditions for general graphs to be two-disjoint-cycle-cover vertex/edge 3-pancyclic, and we also prove that the n-dimensional crossed cube CQn is two-disjoint-cycle-cover 4-pancyclic for n≥3, vertex 4-pancyclic for n≥5, and edge 6-pancyclic for n≥5.