The Panpositionable Pancyclicity of Locally Twisted Cubes

Hon-Chan CHEN  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E101-D   No.12   pp.2902-2907
Publication Date: 2018/12/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018PAP0006
Type of Manuscript: Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking)
Category: Graph Algorithms
Keyword: 
cycle embedding,  pancyclicity,  locally twisted cube,  interconnection network,  

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


Summary: 
In a multiprocessor system, processors are connected based on various types of network topologies. A network topology is usually represented by a graph. Let G be a graph and u, v be any two distinct vertices of G. We say that G is pancyclic if G has a cycle C of every length l(C) satisfying 3≤l(C)≤|V(G)|, where |V(G)| denotes the total number of vertices in G. Moreover, G is panpositionably pancyclic from r if for any integer m satisfying $r leq m leq rac{|V(G)|}{2}$, G has a cycle C containing u and v such that dC(u,v)=m and 2ml(C)≤|V(G)|, where dC(u,v) denotes the distance of u and v in C. In this paper, we investigate the panpositionable pancyclicity problem with respect to the n-dimensional locally twisted cube LTQn, which is a popular topology derived from the hypercube. Let D(LTQn) denote the diameter of LTQn. We show that for n≥4 and for any integer m satisfying $D(LTQ_n) + 2 leq m leq rac{|V(LTQ_n)|}{2}$, there exists a cycle C of LTQn such that dC(u,v)=m, where (i) 2m+1≤l(C)≤|V(LTQn)| if m=D(LTQn)+2 and n is odd, and (ii) 2ml(C)≤|V(LTQn)| otherwise. This improves on the recent result that u and v can be positioned with a given distance on C only under the condition that l(C)=|V(LTQn)|. In parallel and distributed computing, if cycles of different lengths can be embedded, we can adjust the number of simulated processors and increase the flexibility of demand. This paper demonstrates that in LTQn, the cycle embedding containing any two distinct vertices with a feasible distance is extremely flexible.