Panconnectivity and edge-pancyclicity of multidimensional torus networks

摘要

In this paper, the (bi)panconnectivity and edge-(bi)pancyclicity of n-dimensional torus networks are investigated. An n-dimensional torus T = T (k_1, k_2,..., k_n) with diameter m_0 =∑_(i=1)~n[k_i/2], where k_i ≥ 3 for i = 1, 2,..., n, is one of the most popular interconnection networks, the k-ary n-cube Q_n~k (=T (k, k,..., k)) is its special class. For any two vertices u and v in T, we determine the set ρ(u, v) of all lengths of (u, v)-paths in T by using path-shortening technique that can be used efficiently to construct the (u, v)-paths in the torus T. In particular, the following results are obtained: (1) The torus T is bipanconnected and edge-bipancyclic; (2) If some k_j ≥ 3 is odd and the other k_i ≥ 4 is even for every i≠j, then the torus T is m1-panconnected, where m_1 = (k_j ? 1)/2 + m_0, and the bound m1 is optimal; (3) If both k_i ≥ 3 and k_j ≥ 3 are odd, then the torus T is m0-panconnected, and the bound m0 is optimal. (4) If some k_j is odd, let k be the minimum over all odd ki, then T is (k + 1)-edge pancyclic and the bound k + 1 is optimal if T≠ Q_n~k, and T is h-edgepancyclic and the bound h = max{k ? 1, 3} is optimal otherwise. Our results strengthen and generalize existing results.