Hongwei Qiao

One-to-one disjoint path routing constitutes an essential traffic model in which one server may transmit data packets to another server via several internally vertex-disjoint paths. It has been thoroughly investigated because it benefits fault-tolerant ability, load balancing, and congestion control. A bipartite graph H with bipartition $V^0$ and $V^1$ is $k^{\ast }$-laceable if for any $u\in V^0$ and $v\in V^1$, there exist k internally vertex-disjoint paths between u and v whose union covers all vertices of H. Let u be a vertex of G, and let $S=\{v_1,v_2,\dots ,v_k\}$ be a subset of $V\left(G\right)\setminus \left\{u\right\}$. A spanning $(u,S)$-fan is a set of internally vertex-disjoint paths $\{P_1,P_2,\dots ,P_k\}$ in G such that $P_i$ connects u to $v_i$ for each $1\le i\le k$, and ${\bigcup }_{i=1}^{k}V\left(P_i\right)=V\left(G\right)$. The multi-dimensional torus network, as a natural generalization of the hypercube, is a widely studied network with a high degree of symmetry. This paper shows that a bipartite torus admits a spanning $(u,S)$-fan, by which it follows that an n-dimensional bipartite torus $T(d_1,d_2,\dots ,d_n)$ is $k^{\ast }$-laceable for every $1\le k\le 2n$. The result is optimal with respect to the degree of the torus.

Embedding cycles into a network topology is crucial for a network simulation. In particular, embedding Hamiltonian cycles is a major requirement for designing good interconnection networks. A graph G is called r-spanning cyclable if, for any r distinct vertices $v_1,v_2,\dots ,v_r$ of G, there exist r cycles $C_1,C_2,\dots ,C_r$ in G such that $v_i$ is on $C_i$ for every i, and every vertex of G is on exactly one cycle $C_i$. If $r=1$, this is the classical Hamiltonian problem. In this paper, we focus on the problem of embedding spanning disjoint cycles in bipartite k-ary n-cubes. Let $k\ge 4$ be even and $n\ge 2$. It is shown that the n-dimensional bipartite k-ary n-cube $Q_n^k$ is m-spanning cyclable with $m\le 2n-1$. Considering the degree of $Q_n^k$, the result is optimal.