Let u and v be any two distinct vertices of an undirected graph G, which is k-connected. For 1 w k, a w-container C(u, v) of a k-connected graph G is a set of w-disjoint paths joining u and v. A w-container C(u, v) of G is a w *-container if it contains all the vertices of G. A graph G is w *-connected if there exists a w *-container between any two distinct vertices. Let κ(G) be the connectivity of G. A graph G is super spanning connected if G is i *-connected for 1 i κ(G). In this paper, we prove that the n-dimensional burnt pancake graph Bn is super spanning connected if and only if n ≠ 2.

An n-dimensional crossed cube, CQn, is a variation of the hypercube. In this paper, we prove that CQn is (n-2)-Hamiltonian and (n-3)-Hamiltonian connected. That is, a ring of length 2n-fv can be embedded in a faulty CQn with fv faulty nodes and fe faulty edges, where fv+fen-2 and n3. In other words, we show that the faulty CQn is still Hamiltonian with n-2 faults. In addition, we also prove that there exists a Hamiltonian path between any pair of vertices in a faulty CQn with n-3 faults. The above results are optimum in the sense that the fault-tolerant Hamiltonicity (fault-tolerant Hamiltonian connectivity respectively) of CQn is at most n-2 (n-3 respectively). A recent result has shown that a ring of length 2n-2fv can be embedded in a faulty hypercube, if fv+fen-1 and n4, with a few additional constraints. Our results, in comparison to the hypercube, show that longer rings can be embedded in CQn without additional constraints.

In this paper, a new family of interconnection networks which we call the Incrementally Extensible Twisted Cube (IETQ) is proposed. The topology of this network is a novel generalization of the twisted cube. It inherits all the merits but without the limitations owned by a twisted cube. First, this proposed IETQ is incrementally extensible and can be adapted for use in any number of nodes; therefore, this network is particularly well suited for the design of a distributed communication network with an arbitrary number of nodes. Second, the vertex connectivity of IETQ is n. Measured by this vertex connectivity, we demonstrate that this network is optimally fault-tolerant . And it is almost regular, because the difference between the maximum and minimum degree of any node in an IETQ is at most one. A shortestpath routing algorithm for IETQ is proposed to generate path for any given pair of vertices in the network. Third, comparing with most of the other competitors, the diameter of this IETQ network is only half in size. This low diameter helps to reduce the internode communication delay. Moreover, IETQ also possesses the property of a pancyclic network. This attractive property would enable us to map rings of any length into the proposed network.