On embedding cycles into faulty twisted cubes

The twisted cube TQ_n is an alternative to the popular hypercube network. Recently, some interesting properties of TQ_n were investigated. In this paper, we study the pancycle problem on faulty twisted cubes. Let f_e and f_v be the numbers of faulty edges and faulty vertices in TQ_n, respectively. We show that, with f_e + f_v ? n − 2, a faulty TQ_n still contains a cycle of length l for every 4 ? l ? ∣V(TQ_n)∣ − f_v and odd integer n ? 3.     

Embedding a long fault-free cycle in a crossed cube with more faulty nodes

The crossed cube is an important variant of the most popular hypercube network for parallel computing. In this paper, we consider the problem of embedding a long fault-free cycle in a crossed cube with more faulty nodes. We prove that for n?5 and f?2n−7, a fault-free cycle of length at least n²−f−(n−5) can be embedded in an n-dimensional crossed cube with f faulty nodes. Our work extends some previously known results in the sense of the maximum number of faulty nodes tolerable in a crossed cube.     

Complete path embeddings in crossed cubes

Crossed cubes are popular variants of hypercubes. In this paper, we study path embeddings between any two distinct nodes in crossed cubes. We prove two important results in the n-dimensional crossed cube: (a) for any two nodes, all paths whose lengths are greater than or equal to the distance between the two nodes plus 2 can be embedded between the two nodes with dilation 1; (b) for any two integers n ? 2 and l with , there always exist two nodes x and y whose distance is l, such that no path of length l + 1 can be embedded between x and y with dilation 1. The obtained results are optimal in the sense that the dilations of path embeddings are all 1. The results are also complete, because the embeddings of paths of all possible lengths between any two nodes are considered.     

Fault-free Hamiltonian cycles in crossed cubes with conditional link faults

The crossed cube, which is a variation of the hypercube, possesses some properties superior to the hypercube. In this paper, assuming that each node is incident with at least two fault-free links, we show that an n-dimensional crossed cube contains a fault-free Hamiltonian cycle, even if there are up to 2n − 5 link faults. The result is optimal with respect to the number of link faults tolerated. We also verify that the assumption is practically meaningful by evaluating its occurrence probability, which is very close to 1.     

Node-pancyclicity and edge-pancyclicity of crossed cubes

Crossed cubes are important variants of the hypercubes. It has been proven that crossed cubes have attractive properties in Hamiltonian connectivity and pancyclicity. In this paper, we study two stronger features of crossed cubes. We prove that the n-dimensional crossed cube is not only node-pancyclic but also edge-pancyclic for n?2. We also show that the similar property holds for hypercubes.     

Embedding meshes into crossed cubes

Crossed cubes are important variants of hypercubes. In this paper, we consider embeddings of meshes in crossed cubes. The major research findings in this paper are: (1) For any integer n ? 1, a 2 × 2ⁿ⁻¹ mesh can be embedded in the n-dimensional crossed cube with dilation 1 and expansion 1. (2) For any integer n ? 4, two node-disjoint 4 × 2ⁿ⁻³ meshes can be embedded in the n-dimensional crossed cube with dilation 1 and expansion 2. The obtained results are optimal in the sense that the dilations of the embeddings are 1. The embedding of the 2 × 2ⁿ⁻¹ mesh is also optimal in terms of expansion because it has the smallest expansion 1.     

Fault-tolerant embedding of meshes/tori in twisted cubes

Twisted cubes are an important class of hypercube-variant interconnection networks for parallel computing. In this paper, we evaluate the fault-tolerant mesh/torus embedding abilities of twisted cubes. By reducing the fault-tolerant mesh/torus embedding problem to the fault-tolerant pancyclicity, we propose several schemes for embedding meshes/tori in faulty twisted cubes. The obtained results reveal another appealing fault-tolerant feature of twisted cubes.     

The panpositionable panconnectedness of augmented cubes

A graph G is panconnected if, for any two distinct vertices x and y of G, it contains an [x, y]-path of length l for each integer l satisfying d_G(x, y) ? l ? ∣V(G)∣ − 1, where d_G(x, y) denotes the distance between vertices x and y in G, and V(G) denotes the vertex set of G. For insight into the concept of panconnectedness, we propose a more refined property, namely panpositionable panconnectedness. Let x, y, and z be any three distinct vertices in a graph G. Then G is said to be panpositionably panconnected if for any d_G(x, z) ? l₁ ? ∣V(G)∣ − d_G(y, z) − 1, it contains a path P such that x is the beginning vertex of P, z is the (l₁ + 1)th vertex of P, and y is the (l₁ + l₂ + 1)th vertex of P for any integer l₂ satisfying d_G(y, z) ? l₂ ? ∣V(G)∣ − l₁ − 1. The augmented cube, proposed by Choudum and Sunitha [6] to be an enhancement of the n-cube Q_n, not only retains some attractive characteristics of Q_n but also possesses many distinguishing properties of which Q_n lacks. In this paper, we investigate the panpositionable panconnectedness with respect to the class of augmented cubes. As a consequence, many topological properties related to cycle and path embedding in augmented cubes, such as pancyclicity, panconnectedness, and panpositionable Hamiltonicity, can be drawn from our results.     

Hamilton-connectivity and cycle-embedding of the Möbius cubes

The recently introduced interconnection network, the Möbius cube, is an important variant of the hypercube. This network has several attractive properties compared with the hypercube. In this paper, we show that the n-dimensional Möbius cube M_n is Hamilton-connected when n?3. Then, by using the Hamilton-connectivity of M_n, we also show that any cycle of length l (4?l?2ⁿ) can be embedded into M_n with dilation 1 (n?2). It is a fact that the n-dimensional hypercube Q_n does not possess these two properties.     

Fault-tolerant pancyclicity of augmented cubes

As an enhancement on the hypercube Qn, the augmented cube AQn, prosed by Choudum and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2) (2002) 71-84], not only retains some favorable properties of Qn but also possesses some embedding properties that Qn does not. For example, AQn is pancyclic, that is, AQn contains cycles of arbitrary length for n?2. This paper shows that AQn remains pancyclic provided faulty vertices and/or edges do not exceed 2n−3 and n?4.     

Conditional fault diameter of crossed cubes

The conditional connectivity and the conditional fault diameter of a crossed cube are studied in this work. The conditional connectivity is the connectivity of an interconnection network with conditional faults, where each node has at least one fault-free neighbor. Based on this requirement, the conditional connectivity of a crossed cube is shown to be 2n−2$2n-2$. Extending this result, the conditional fault diameter of a crossed cube is also shown to be D(C_Qn)+3$D\left(C{Q}_n\right)+3$ as a set of 2n−3$2n-3$ node failures. This indicates that the conditional fault diameter of a crossed cube is increased by three compared to the fault-free diameter of a crossed cube. The conditional fault diameter of a crossed cube is approximately half that of the hypercube. In this respect, the crossed cube is superior to the hypercube.     

Constructing the nearly shortest path in crossed cubes

A graph G is panconnected if each pair of distinct vertices u,v∈V(G) are joined by a path of length l for all d_G(u,v)?l?|V(G)|-1, where d_G(u,v) is the length of a shortest path joining u and v in G. Recently, Fan et. al. [J. Fan, X. Lin, X. Jia, Optimal path embedding in crossed cubes, IEEE Trans. Parall. Distrib. Syst. 16 (2) (2005) 1190-1200, J. Fan, X. Jia, X. Lin, Complete path embeddings in crossed cubes, Inform. Sci. 176 (22) (2006) 3332-3346] and Xu et. al. [J.M. Xu, M.J. Ma, M. Lu, Paths in Möbius cubes and crossed cubes, Inform. Proc. Lett. 97 (3) (2006) 94-97] both proved that n-dimensional crossed cube, CQ_n, is almost panconnected except the path of length d_CQn(u,v)+1 for any two distinct vertices u,v∈V(CQ_n). In this paper, we give a necessary and sufficient condition to check for the existence of paths of length d_CQn(u,v)+1, called the nearly shortest paths, for any two distinct vertices u,v in CQ_n. Moreover, we observe that only some pair of vertices have no nearly shortest path and we give a construction scheme for the nearly shortest path if it exists.     

Embedding a family of disjoint multi-dimensional meshes into a crossed cube

Crossed cubes are an important class of hypercube variants. This paper addresses how to embed a family of disjoint multi-dimensional meshes into a crossed cube. We prove that for n?4 and 1?m?⌊n/2⌋−1, a family of m² disjoint k-dimensional meshes of size t₁²×t₂²×?×tk² each can be embedded in an n-dimensional crossed cube with unit dilation, where and max1?i?k{ti}?n−2m−1. This result means that a family of mesh-structured parallel algorithms can be executed on a same crossed cube efficiently and in parallel. Our work extends some recently obtained results.     

Fault-tolerant hamiltonian laceability of hypercubes

It is known that every hypercube Q_n is a bipartite graph. Assume that n?2 and F is a subset of edges with |F|?n−2. We prove that there exists a hamiltonian path in Q_n−F between any two vertices of different partite sets. Moreover, there exists a path of length 2ⁿ−2 between any two vertices of the same partite set. Assume that n?3 and F is a subset of edges with |F|?n−3. We prove that there exists a hamiltonian path in Q_n−{v}−F between any two vertices in the partite set without v. Furthermore, all bounds are tight.     

Independent spanning trees on twisted cubes

Multiple independent spanning trees have applications to fault tolerance and data broadcasting in distributed networks. There are two versions of the n independent spanning trees conjecture. The vertex (edge) conjecture is that any n-connected (n-edge-connected) graph has n vertex-independent spanning trees (edge-independent spanning trees) rooted at an arbitrary vertex. Note that the vertex conjecture implies the edge conjecture. The vertex and edge conjectures have been confirmed only for n-connected graphs with n≤4, and they are still open for arbitrary n-connected graph when n≥5. In this paper, we confirm the vertex conjecture (and hence also the edge conjecture) for the n-dimensional twisted cube TQ_n by providing an O(NlogN) algorithm to construct n vertex-independent spanning trees rooted at any vertex, where N denotes the number of vertices in TQ_n. Moreover, all independent spanning trees rooted at an arbitrary vertex constructed by our construction method are isomorphic and the height of each tree is n+1 for any integer n≥2.     

Paths in Möbius cubes and crossed cubes

The Möbius cube MQn and the crossed cube CQn are two important variants of the hypercube Qn. This paper shows that for any two different vertices u and v in G∈{MQn,CQn} with n?3, there exists a uv-path of every length from dG(u,v)+2 to n²−1 except for a shortest uv-path, where dG(u,v) is the distance between u and v in G. This result improves some known results.     

Embedding a family of disjoint 3D meshes into a crossed cube

Crossed cubes are an important class of hypercube variants. This paper addresses how to embed a family of disjoint 3D meshes into a crossed cube. Two major contributions of this paper are: (1) for n?4, a family of two disjoint 3D meshes of size 2×2×2^n-3 can be embedded in an n-D crossed cube with unit dilation and unit expansion, and (2) for n?6, a family of four disjoint 3D meshes of size 4×2×2^n-5 can be embedded in an n-D crossed cube with unit dilation and unit expansion. These results mean that a family of two or four 3D-mesh-structured parallel algorithms can be executed on a same crossed cube efficiently and in parallel. Our work extends the results recently obtained by Fan and Jia [J. Fan, X. Jia, Embedding meshes into crossed cubes, Information Sciences 177(15) (2007) 3151-3160].     

The twisted crossed cube

The topology of interconnection networks plays an important role in the performance of parallel and distributed computing systems. In this paper, we propose a new interconnection network called twisted crossed cube (TCQ_n) and investigate its basic network properties in terms of the regularity, connectivity, fault tolerance, recursiveness, hamiltonicity and ability to simulate other architectures, and so on. Then, we develop an effective routing algorithm Route (u, v) for TCQ_n that takes no more than d(u, v) + 1 steps for any two nodes (u, v) to communicate with each other, and the routing process shows that the diameter, wide diameter, and fault‐tolerant diameter of TCQ_n are about half of the corresponding diameters of the equivalent hypercube with the same dimension. In the end, by combining TCQ_n with crossed cube (CQ_n), we propose a preferable dynamic network structure, that is, the dynamic crossed cube, which has the same network diameter as TCQ_n/CQ_n and better properties in other respects, for example, its connection complexity is half of that of TCQ_n/CQ_n when the network scale is large enough, and the number of its average routing steps is also much smaller than that in TCQ_n/CQ_n. Copyright © 2015 John Wiley & Sons, Ltd.     

Improving the panconnectedness property of locally twisted cubes

The n-dimensional locally twisted cube LTQ_n is a promising alternative to the hypercube because of its great properties. Not only is LTQ_n n-connected, but also meshes, torus, and edge-disjoint Hamiltonian cycles can embed in it. Ma and Xu [Panconnectivity of locally twisted cubes, Appl. Math. Lett. 19 (2006), pp. 681–685] investigated the panconnectivity of LTQ_n for flexible routing. In this paper, we combine panconnectivity with Hamiltonian connectedness to define Hamiltonian r-panconnectedness: a graph G of m vertices, m≥3, is Hamiltonian r-panconnected if for any three distinct vertices x, y, and z of G there exists a Hamiltonian path P of G such that P(1)=x, P(l+1)=y, and P(m)=z for every r≤l≤m?1?r, where P(i) denotes the ith vertex of P for 1≤i≤m. Then, we show that LTQ_n is Hamiltonian n-panconnected for n≥5. This property admits the path embedding via an intermediate node at any prescribed position, and our result achieves an improvement over that of Ma and Xu.