Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes

Fault-tolerant broadcasting and secure message distribution are important issues for numerous applications in networks. It is a common idea to design multiple spanning trees with a specific property in the underlying graph of a network to serve as a broadcasting scheme or a distribution protocol for receiving high levels of fault-tolerance and of security. A set of spanning trees in a graph is said to be edge-disjoint if these trees are rooted at the same node without sharing any common edge. Hsieh and Tu [S.-Y. Hsieh, C.-J. Tu, Constructing edge-disjoint spanning trees in locally twisted cubes, Theoretical Computer Science 410 (2009) 926-932] recently presented an algorithm for constructing n edge-disjoint spanning trees in an n-dimensional locally twisted cube. In this paper, we prove that indeed all spanning trees constructed by their algorithm are independent, i.e., any two spanning trees are rooted at the same node, say r, and for any other node v≠r, the two different paths from v to r, one path in each tree, are internally node-disjoint.     

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.     

One-to-one communication in twisted cubes under restricted connectivity

The dimensions of twisted cubes are only limited to odd integers. In this paper, we first extend the dimensions of twisted cubes to all positive integers. Then, we introduce the concept of the restricted faulty set into twisted cubes. We further prove that under the condition that each node of the n-dimensional twisted cube TQ _n has at least one fault-free neighbor, its restricted connectivity is 2n − 2, which is almost twice as that of TQ _n under the condition of arbitrary faulty nodes, the same as that of the n-dimensional hypercube. Moreover, we provide an O(NlogN) fault-free unicast algorithm and simulations result of the expected length of the fault-free path obtained by our algorithm, where N denotes the node number of TQ _n . Finally, we propose a polynomial algorithm to check whether the faulty node set satisfies the condition that each node of the n-dimensional twisted cube TQ _n has at least one fault-free neighbor.     

Augmented k-ary n-cubes

We define an interconnection network AQ_n,k which we call the augmented k-ary n-cube by extending a k-ary n-cube in a manner analogous to the existing extension of an n-dimensional hypercube to an n-dimensional augmented cube. We prove that the augmented k-ary n-cube AQ_n,k has a number of attractive properties (in the context of parallel computing). For example, we show that the augmented k-ary n-cube AQ_n,k: is a Cayley graph, and so is vertex-symmetric, but not edge-symmetric unless n = 2; has connectivity 4n − 2 and wide-diameter at most max{(n − 1)k − (n − 2), k + 7}; has diameter , when n = 2; and has diameter at most , for n ? 3 and k even, and at most , for n ? 3 and k odd.     

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.     

Geodesic pancyclicity of twisted cubes

The hypercube is one of the most popular interconnection networks since it has simple structure and is easy to implement. An n-dimensional twisted cube, TQ_n, is an important variation of the hypercube Q_n and preserves many of its desirable properties. The problem of embedding linear arrays and cycles into a host graph has attracted substantial attention in recent years. The geodesic cycle embedding problem is for any two distinct vertices, to find all the possible lengths of cycles that include a shortest path joining them. In this paper, we prove that TQ_n is geodesic 2-pancyclic for each odd integer n ? 3. This result implies that TQ_n is edge-pancyclic for each odd integer n ? 3. Moreover, TQ_n × K₂ is also demonstrated to be geodesic 4-pancyclic.     

A dynamic programming algorithm for simulation of a multi-dimensional torus in a crossed cube

The torus is a popular interconnection topology and several commercial multicomputers use a torus as the basis of their communication network. Moreover, there are many parallel algorithms with torus-structured and mesh-structured task graphs have been developed. If one network can embed a mesh or torus network, the algorithms with mesh-structured or torus-structured can also be used in this network. Thus, the problem of embedding meshes or tori into networks is meaningful for parallel computing. In this paper, we prove that for n ? 6 and 1 ? m ? ⌈n/2⌉ − 1, a family of 2^m disjoint k-dimensional tori of size 2^s₁×2^s₂×?×2^s_k each can be embedded in an n-dimensional crossed cube with unit dilation, where each s_i ? 2, , and max_1?i?k{s_i} ? 3 if n is odd and ; otherwise, max_1?i?k{s_i} ? n − 2m − 1. A new concept, cycle skeleton, is proposed to construct a dynamic programming algorithm for embedding a desired torus into the crossed cube. Furthermore, the time complexity of the algorithm is linear with respect to the size of desired torus. As a consequence, a family of disjoint tori can be simulated on the same crossed cube efficiently and in parallel.     

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.     

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 ⁿ .     

Maximum induced subgraph of a recursive circulant

The recursive circulant RC(n²,4) enjoys several attractive topological properties. Let max_?G(m) denote the maximum number of edges in a subgraph of graph G induced by m nodes. In this paper, we show that , where p₀>p₁>?>pr are nonnegative integers defined by . We then apply this formula to find the bisection width of RC(n²,4). The conclusion shows that, as n-dimensional cube, RC(n²,4) enjoys a linear bisection width.     

A compact data structure for representing a dynamic multiset

We develop a data structure for maintaining a dynamic multiset that uses bits and O(1) words, in addition to the space required by the n elements stored, supports searches in worst-case time and updates in amortized time. Compared to earlier data structures, we improve the space requirements from O(n) bits to bits, but the running time of updates is amortized, not worst-case.     

On plane spanning trees and cycles of multicolored point sets with few intersections

Let P₁,…,Pk be a collection of disjoint point sets in R² in general position. We prove that for each 1?i?k we can find a plane spanning tree Ti of Pi such that the edges of T₁,…,Tk intersect at most , where n is the number of points in P₁∪?∪Pk. If the intersection of the convex hulls of P₁,…,Pk is nonempty, we can find k spanning cycles such that their edges intersect at most (k−1)n times, this bound is tight. We also prove that if P and Q are disjoint point sets in general position, then the minimum weight spanning trees of P and Q intersect at most 8n times, where |P∪Q|=n (the weight of an edge is its length).     

Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes

The n-dimensional hypercube network Q_n is one of the most popular interconnection networks since it has simple structure and is easy to implement. The n-dimensional locally twisted cube LTQ_n, an important variation of the hypercube, has the same number of nodes and the same number of connections per node as Q_n. One advantage of LTQ_n is that the diameter is only about half of the diameter of Q_n. Recently, some interesting properties of LTQ_n have been investigated in the literature. The presence of edge-disjoint Hamiltonian cycles provides an advantage when implementing algorithms that require a ring structure by allowing message traffic to be spread evenly across the interconnection network. The existence of two edge-disjoint Hamiltonian cycles in locally twisted cubes has remained unknown. In this paper, we prove that the locally twisted cube LTQ_n with n?4 contains two edge-disjoint Hamiltonian cycles. Based on the proof of existence, we further provide an O(n2ⁿ)-linear time algorithm to construct two edge-disjoint Hamiltonian cycles in an n-dimensional locally twisted cube LTQ_n with n?4, where LTQ_n contains 2ⁿ nodes and n2ⁿ⁻¹ edges.     

Fault-Tolerant Hamiltonicity of Twisted Cubes

The twisted cube TQ_n, is derived by changing some connection of hypercube Q_n according to specific rules. Recently, many topological properties of this variation cube are studied. In this paper, we consider a faulty twisted n-cube with both edge and/or node faults. Let F be a subset of V(TQ_n)∩E(TQ_n), we prove that TQ_n−F remains hamiltonian if |F|⩽n−2. Moreover, we prove that there exists a hamiltonian path in TQ_n−F joining any two vertices u, v in V(TQ_n)−F if |F|⩽n−3. The result is optimum in the sense that the fault-tolerant hamiltonicity (fault-tolerant hamiltonian connectivity respectively) of TQ_n is at most n−2 (n−3 respectively).     

Optimal fault-tolerant embedding of paths in twisted cubes

The twisted cube is an important variation of the hypercube. It possesses many desirable properties for interconnection networks. In this paper, we study fault-tolerant embedding of paths in twisted cubes. Let _TQn(V,E)${\mathit{TQ}}_n(V,E)$ denote the n-dimensional twisted cube. We prove that a path of length l   can be embedded between any two distinct nodes with dilation 1 for any faulty set F⊂V(_TQn)∪E(_TQn)$F\subset V({\mathit{TQ}}_n)\cup E({\mathit{TQ}}_n)$ with |F|?n-3$\left|F\right|?n-3$ and any integer l   with 2^n-1-1?l?|V(_TQn-F)|-1$2^{n-1}-1?l?|V({\mathit{TQ}}_n-F)|-1$ (n?3$n?3$). This result is optimal in the sense that the embedding has the smallest dilation 1. The result is also complete in the sense that the two bounds on path length l   and faulty set size |F|$\left|F\right|$ for a successful embedding are tight. That is, the result does not hold if l?2^n-1-2$l?2^{n-1}-2$ or |F|?n-2$\left|F\right|?n-2$. We also extend the result on (n-3)$(n-3)$-Hamiltonian connectivity of _TQn${\mathit{TQ}}_n$ in the literature.     

A note on stutter-invariant PLTL

Peled and Wilke proved that every stutter-invariant propositional linear temporal property is expressible in Propositional Linear Temporal Logic (PLTL) without  ?  (next) operators. To eliminate next operators, a translation τ which converts a stutter-invariant PLTL formula ? to an equivalent formula τ(?) not containing  ?  operators has been given. By τ, for any formula , where φ contains no  ?  operators, a formula with the length of O(n⁴|φ|) is always produced, where n is the number of distinct propositions in ?, and |φ| is the number of symbols appearing in φ. Etessami presented an improved translation τ^′. By τ^′, for , a formula with the length of O(n×n²|φ|) is always produced. We further improve Etessami's result in the worst case to O(n×n²|φ|) by providing a new translation τ^″, and we show that the worst case will never occur.     

Constructing independent spanning trees for locally twisted cubes

The independent spanning trees (ISTs) problem attempts to construct a set of pairwise independent spanning trees and it has numerous applications in networks such as data broadcasting, scattering and reliable communication protocols. The well-known ISTs conjecture, Vertex/Edge Conjecture, states that any n-connected/n-edge-connected graph has n vertex-ISTs/edge-ISTs rooted at an arbitrary vertex r. It has been shown that the Vertex Conjecture implies the Edge Conjecture. In this paper, we consider the independent spanning trees problem on the n-dimensional locally twisted cube LTQ_n. The very recent algorithm proposed by Hsieh and Tu (2009) [12] is designed to construct n edge-ISTs rooted at vertex 0 for LTQ_n. However, we find out that LTQ_n is not vertex-transitive when n≥4; therefore Hsieh and Tu’s result does not solve the Edge Conjecture for LTQ_n. In this paper, we propose an algorithm for constructing n vertex-ISTs for LTQ_n; consequently, we confirm the Vertex Conjecture (and hence also the Edge Conjecture) for LTQ_n.