The spined cube: A new hypercube variant with smaller diameter

Bijective connection graphs (in brief, BC graphs) are a family of hypercube variants, which contains hypercubes, twisted cubes, crossed cubes, Möbius cubes, locally twisted cubes, etc. It was proved that the smallest diameter of all the known n-dimensional bijective connection graphs (BC graphs) is , given a fixed dimension n. An important question about the smallest diameter among all the BC graphs is: Does there exist a BC graph whose diameter is less than the known BC graphs such as crossed cubes, twisted cubes, Möbius cubes, etc., with the same dimension? This paper answers this question. In this paper, we find that there exists a kind of BC graphs called spined cubes and we prove that the n-dimensional spined cube has the diameter ⌈n/3⌉+3 for any integer n with n?14. It is the first time in literature that a hypercube variant with such a small diameter is presented.     

Efficient unicast in bijective connection networks with the restricted faulty node set

The connectivity is an important criteria to measure the fault-tolerant performance of a graph. However, the connectivity based on the condition of the set of arbitrary faulty nodes is generally lower. In this paper, in order to heighten this measure, we introduce the restricted connectivity into bijective connection networks. First, we prove that the probability that all the neighbors of an arbitrary node becomes faulty in any n-dimensional bijective connection network X_n is very low when n becomes sufficient large. Then, we give a constructive proof that under the condition that each node of an n-dimensional bijective connection network X_n has at least one fault-free neighbor, its restricted connectivity is 2n − 2, about half of the connectivity of X_n. Finally, by our constructive proof, we give an O(n) algorithm to get a reliable path of length at most n + 3⌈log₂∣F∣⌉ + 1 between any two fault-free nodes in an n-dimensional bijective connection network. In particular, since the family of BC networks contains hypercubes, crossed cubes, Möbius cubes, etc., our algorithm is appropriate for these cubes.     

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.     

An efficient fault-tolerant routing algorithm in bijective connection networks with restricted faulty edges

In this paper, we study fault-tolerant routing in bijective connection networks with restricted faulty edges. First, we prove that the probability that all the incident edges of an arbitrary node become faulty in an n-dimensional bijective connection network, denoted by X_n, is extremely low when n becomes sufficient large. Then, we give an O(n) algorithm to find a fault-free path of length at most n+3⌈log₂∣F∣⌉+1 between any two different nodes in X_n if each node of X_n has at least one fault-free incident edge and the number of faulty edges is not more than 2n−3. In fact, we also for the first time provide an upper bound of the fault diameter of all the bijective connection networks with the restricted faulty edges. Since the family of BC networks contains hypercubes, crossed cubes, Möbius cubes, etc., all the results are appropriate for these cubes.     

On conditional diagnosability and reliability of the BC networks

An n-dimensional bijective connection network (in brief, BC network), denoted by X _n , is an n-regular graph with 2 ⁿ nodes and n2 ^n?1 edges. Hypercubes, crossed cubes, twisted cubes, and Möbius cubes all belong to the class of BC networks (Fan and He in Chin. J. Comput. 26(1):84–90, [2003]). We prove that the super connectivity of X _n is 2n?2 for n≥3 and the conditional diagnosability of X _n is 4n?7 for n≥5. As a corollary of this result, we obtain the super connectivity and conditional diagnosability of the hypercubes, twisted cubes, crossed cubes, and Möbius cubes.     

A fast fault-identification algorithm for bijective connection graphs using the PMC model

Diagnosis of reliability is an important topic for interconnection networks. Under the classical PMC model, Dahura and Masson [5] proposed a polynomial time algorithm with time complexity O(N^2.5) to identify all faulty nodes in an N-node network. This paper addresses the fault diagnosis of so called bijective connection (BC) graphs including hypercubes, twisted cubes, locally twisted cubes, crossed cubes, and Möbius cubes. Utilizing a helpful structure proposed by Hsu and Tan [20] that was called the extending star by Lin et al. [24], and noting the existence of a structured Hamiltonian path within any BC graph, we present a fast diagnostic algorithm to identify all faulty nodes in O(N) time, where N = 2ⁿ, n ? 4, stands for the total number of nodes in the n-dimensional BC graph. As a result, this algorithm is significantly superior to Dahura–Masson’s algorithm when applied to BC graphs.     

Fault-tolerant analysis of a class of networks

In this paper, we explore the 2-extraconnectivity of a special class of graphs G(G₀,G₁;M) proposed by Chen et al. [Y.-C. Chen, J.J.M. Tan, L.-H. Hsu, S.-S. Kao, Super-connectivity and super edge-connectivity for some interconnection networks, Applied Mathematics and Computation 140 (2003) 245-254]. As applications of the results, we obtain that the 2-extraconnectivities of several well-known interconnection networks, such as hypercubes, twisted cubes, crossed cubes, Möbius cubes and locally twisted cubes, are all equal to 3n−5 when their dimension n is not less than 8. That is, when n?8, at least 3n−5 vertices must be removed to disconnect any one of these n-dimensional networks provided that the removal of these vertices does not isolate a vertex or an edge.     

Node-pancyclicity and edge-pancyclicity of hypercube variants

Twisted cubes, crossed cubes, Möbius cubes, and locally twisted cubes are some of the widely studied hypercube variants. The 4-pancyclicity of twisted cubes, crossed cubes, Möbius cubes, locally twisted cubes and the 4-edge-pancyclicity of twisted cubes, crossed cubes, Möbius cubes are proven in [C.P. Chang, J.N. Wang, L.H. Hsu, Topological properties of twisted cube, Inform. Sci. 113 (1999) 147-167; C.P. Chang, T.Y. Sung, L.H. Hsu, Edge congestion and topological properties of crossed cubes, IEEE Trans. Parall. Distr. 11 (1) (2000) 64-80; J. Fan, Hamilton-connectivity and cycle embedding of the Möbius cubes, Inform. Process. Lett. 82 (2002) 113-117; X. Yang, G.M. Megson, D.J. Evans, Locally twisted cubes are 4-pancyclic, Appl. Math. Lett. 17 (2004) 919-925; J. Fan, N. Yu, X. Jia, X. Lin, Embedding of cycles in twisted cubes with edge-pancyclic, Algorithmica, submitted for publication; J. Fan, X. Lin, X. Jia, Node-pancyclic and edge-pancyclic of crossed cubes, Inform. Process. Lett. 93 (2005) 133-138; M. Xu, J.M. Xu, Edge-pancyclicity of Möbius cubes, Inform. Process. Lett. 96 (2005) 136-140], respectively. It should be noted that 4-edge-pancyclicity implies 4-node-pancyclicity which further implies 4-pancyclicity. In this paper, we outline an approach to prove the 4-edge-pancyclicity of some hypercube variants and we prove in particular that Möbius cubes and locally twisted cubes are 4-edge-pancyclic.     

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.     

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.     

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.     

Embedding of Cycles in Twisted Cubes with Edge-Pancyclic

In this paper, we study the embedding of cycles in twisted cubes. It has been proven in the literature that, for any integer l, 4≤l≤2 ⁿ , a cycle of length l can be embedded with dilation 1 in an n-dimensional twisted cube, n≥3. We obtain a stronger result of embedding of cycles with edge-pancyclic. We prove that, for any integer l, 4≤l≤2 ⁿ , and a given edge (x,y) in an n-dimensional twisted cube, n≥3, a cycle C of length l can be embedded with dilation 1 in the n-dimensional twisted cube such that (x,y) is in C in the twisted cube. Based on the proof of the edge-pancyclicity of twisted cubes, we further provide an O(llog l+n ²+nl) algorithm to find a cycle C of length l that contains (u,v) in TQ _n for any (u,v)∈E(TQ _n ) and any integer l with 4≤l≤2 ⁿ .     

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.     

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 meshes into locally twisted cubes

As a newly introduced interconnection network for parallel computing, the locally twisted cube possesses many desirable properties. In this paper, mesh embeddings in locally twisted cubes are studied. Let LTQ_n(V, E) denote the n-dimensional locally twisted cube. We present three major results in this paper: (1) For any integer n ? 1, a 2 × 2ⁿ⁻¹ mesh can be embedded in LTQ_n with dilation 1 and expansion 1. (2) For any integer n ? 4, two node-disjoint 4 × 2ⁿ⁻³ meshes can be embedded in LTQ_n with dilation 1 and expansion 2. (3) For any integer n ? 3, a 4  × (2ⁿ⁻² − 1) mesh can be embedded in LTQ_n with dilation 2. The first two results are optimal in the sense that the dilations of all embeddings are 1. The embedding of the 2 × 2ⁿ⁻¹ mesh is also optimal in terms of expansion. We also present the analysis of 2p × 2q mesh embedding in locally twisted cubes.     

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.     

Exact exponential-time algorithms for finding bicliques

Due to a large number of applications, bicliques of graphs have been widely considered in the literature. This paper focuses on non-induced bicliques. Given a graph G=(V,E) on n vertices, a pair (X,Y), with X,Y⊆V, X∩Y=∅, is a non-induced biclique if {x,y}∈E for any x∈X and y∈Y. The NP-complete problem of finding a non-induced (k₁,k₂)-biclique asks to decide whether G contains a non-induced biclique (X,Y) such that |X|=k₁ and |Y|=k₂. In this paper, we design a polynomial-space O(n^1.6914)-time algorithm for this problem. It is based on an algorithm for bipartite graphs that runs in time O(n^1.30052). In deriving this algorithm, we also exhibit a relation to the spare allocation problem known from memory chip fabrication. As a byproduct, we show that the constraint bipartite vertex cover problem can be solved in time O(n^1.30052).     

Fault-tolerant edge-pancyclicity of locally twisted cubes

The n-dimensional locally twisted cube LTQ_n is a new variant of the hypercube, which possesses some properties superior to the hypercube. This paper investigates the fault-tolerant edge-pancyclicity of LTQ_n, and shows that if LTQ_n (n ? 3) contains at most n − 3 faulty vertices and/or edges then, for any fault-free edge e and any integer ? with 6 ? ? ? 2ⁿ − f_v, there is a fault-free cycle of length ? containing the edge e, where f_v is the number of faulty vertices. The result is optimal in some senses. The proof is based on the recursive structure of LTQ_n.     

Edge-pancyclicity of Möbius cubes

The Möbius cube Mn is a variant of the hypercube Qn and has better properties than Qn with the same number of links and processors. It has been shown by Fan [J. Fan, Hamilton-connectivity and cycle-embedding of Möbius cubes, Inform. Process. Lett. 82 (2002) 113-117] and Huang et al. [W.-T. Huang, W.-K. Chen, C.-H. Chen, Pancyclicity of Möbius cubes, in: Proc. 9th Internat. Conf. on Parallel and Distributed Systems (ICPADS'02), 17-20 Dec. 2002, pp. 591-596], independently, that Mn contains a cycle of every length from 4 to n². In this paper, we improve this result by showing that every edge of Mn lies on a cycle of every length from 4 to n² inclusive.     

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.