On the path-connectivity, vertex-pancyclicity, and edge-pancyclicity of crossed cubes | |
Yang X.3; Evans D.J.4; Megson G.M.1; Tang Y.3 | |
2005-03-01 | |
Source Publication | Neural, Parallel and Scientific Computations |
ISSN | 10615369 |
Volume | 13Issue:1Pages:107-118 |
Abstract | Crossed cube architecture is an alternative to interconnection network due to its half diameter and better graph embedding capability compared with hypercube of the same size. Path and cycle structures are essential for parallel computation since many typical problems can be efficiently solved on these structures. This paper addresses the existence of paths or cycles with specified properties in an n-dimensional crossed cube, CQ. We first propose the notions of path-connectivity, vertex-pancyclicity, and edge-pancyclicity for a graph. We then prove that for any two distinct vertices on CQ at a distance of d apart and each integer l satisfying d + 2 ≤ l ≤ V(CQ) - 1, CQ has a path of length l between this pair of vertices. Based on this, we conclude that (1) for each vertex on CQ and each integer l satisfying 4 ≤ l ≤ V(CQ) , CQ has a cycle of length l that contains this vertex, and (2) for each edge of CQ and each integer l satisfying 4 ≤ l ≤ V(CQ) , CQ has a cycle of length l that contains this edge. Due to the fact that hypercubes do not share these properties, crossed cubes show more advantages over hypercubes. © Dynamic Publishers, Inc. |
Keyword | Connectivity Crossed cube Interconnection network Pancyclicity |
URL | View the original |
Language | 英語 |
Fulltext Access | |
Document Type | Journal article |
Collection | University of Macau |
Affiliation | 1.University of Reading 2.Hong Kong Baptist University 3.Chongqing University 4.Loughborough University |
Recommended Citation GB/T 7714 | Yang X.,Evans D.J.,Megson G.M.,et al. On the path-connectivity, vertex-pancyclicity, and edge-pancyclicity of crossed cubes[J]. Neural, Parallel and Scientific Computations,2005,13(1):107-118. |
APA | Yang X.,Evans D.J.,Megson G.M.,&Tang Y..(2005).On the path-connectivity, vertex-pancyclicity, and edge-pancyclicity of crossed cubes.Neural, Parallel and Scientific Computations,13(1),107-118. |
MLA | Yang X.,et al."On the path-connectivity, vertex-pancyclicity, and edge-pancyclicity of crossed cubes".Neural, Parallel and Scientific Computations 13.1(2005):107-118. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment