The Panpositionable Pancyclicity of Locally Twisted Cubes

Hon-Chan CHEN

doi:10.1587/transinf.2018PAP0006

IEICE TRANSACTIONS on Information

The Panpositionable Pancyclicity of Locally Twisted Cubes

Hon-Chan CHEN

Full Text Views

0

Cite this

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 d_C(u,v)=m and 2m≤l(C)≤|V(G)|, where d_C(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 LTQ_n, which is a popular topology derived from the hypercube. Let D(LTQ_n) denote the diameter of LTQ_n. 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 LTQ_n such that d_C(u,v)=m, where (i) 2m+1≤l(C)≤|V(LTQ_n)| if m=D(LTQ_n)+2 and n is odd, and (ii) 2m≤l(C)≤|V(LTQ_n)| 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(LTQ_n)|. 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 LTQ_n, the cycle embedding containing any two distinct vertices with a feasible distance is extremely flexible.

Publication: IEICE TRANSACTIONS on Information Vol.E101-D No.12 pp.2902-2907

Publication Date: 2018/12/01

Publicized: 2018/09/18

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

Authors

Hon-Chan CHEN
National Chin-Yi University of Technology

Keyword

cycle embedding, pancyclicity, locally twisted cube, interconnection network

Cite this

Copy

Hon-Chan CHEN, "The Panpositionable Pancyclicity of Locally Twisted Cubes" in IEICE TRANSACTIONS on Information, vol. E101-D, no. 12, pp. 2902-2907, December 2018, doi: 10.1587/transinf.2018PAP0006.
Abstract: 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 d_C(u,v)=m and 2m≤l(C)≤|V(G)|, where d_C(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 LTQ_n, which is a popular topology derived from the hypercube. Let D(LTQ_n) denote the diameter of LTQ_n. 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 LTQ_n such that d_C(u,v)=m, where (i) 2m+1≤l(C)≤|V(LTQ_n)| if m=D(LTQ_n)+2 and n is odd, and (ii) 2m≤l(C)≤|V(LTQ_n)| 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(LTQ_n)|. 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 LTQ_n, the cycle embedding containing any two distinct vertices with a feasible distance is extremely flexible.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018PAP0006/_p

Copy

@ARTICLE{e101-d_12_2902,
author={Hon-Chan CHEN, },
journal={IEICE TRANSACTIONS on Information},
title={The Panpositionable Pancyclicity of Locally Twisted Cubes},
year={2018},
volume={E101-D},
number={12},
pages={2902-2907},
abstract={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 d_C(u,v)=m and 2m≤l(C)≤|V(G)|, where d_C(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 LTQ_n, which is a popular topology derived from the hypercube. Let D(LTQ_n) denote the diameter of LTQ_n. 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 LTQ_n such that d_C(u,v)=m, where (i) 2m+1≤l(C)≤|V(LTQ_n)| if m=D(LTQ_n)+2 and n is odd, and (ii) 2m≤l(C)≤|V(LTQ_n)| 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(LTQ_n)|. 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 LTQ_n, the cycle embedding containing any two distinct vertices with a feasible distance is extremely flexible.},
keywords={},
doi={10.1587/transinf.2018PAP0006},
ISSN={1745-1361},
month={December},}

Copy

TY - JOUR
TI - The Panpositionable Pancyclicity of Locally Twisted Cubes
T2 - IEICE TRANSACTIONS on Information
SP - 2902
EP - 2907
AU - Hon-Chan CHEN
PY - 2018
DO - 10.1587/transinf.2018PAP0006
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E101-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2018
AB - 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 d_C(u,v)=m and 2m≤l(C)≤|V(G)|, where d_C(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 LTQ_n, which is a popular topology derived from the hypercube. Let D(LTQ_n) denote the diameter of LTQ_n. 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 LTQ_n such that d_C(u,v)=m, where (i) 2m+1≤l(C)≤|V(LTQ_n)| if m=D(LTQ_n)+2 and n is odd, and (ii) 2m≤l(C)≤|V(LTQ_n)| 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(LTQ_n)|. 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 LTQ_n, the cycle embedding containing any two distinct vertices with a feasible distance is extremely flexible.
ER -

IEICE TRANSACTIONS on Information