Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872150 | Discrete Applied Mathematics | 2014 | 13 Pages |
Abstract
In this paper, the (bi)panconnectivity and edge-(bi)pancyclicity of n-dimensional torus networks are investigated. An n-dimensional torus T=T(k1,k2,â¦,kn) with diameter m0=âi=1nâki/2â, where kiâ¥3 for i=1,2,â¦,n, is one of the most popular interconnection networks, the k-ary n-cube Qnk (=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 kjâ¥3 is odd and the other kiâ¥4 is even for every iâ j, then the torus T is m1-panconnected, where m1=(kjâ1)/2+m0, and the bound m1 is optimal; (3) If both kiâ¥3 and kjâ¥3 are odd, then the torus T is m0-panconnected, and the bound m0 is optimal. (4) If some kj 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â Qnk, and T is h-edge-pancyclic and the bound h=max{kâ1,3} is optimal otherwise. Our results strengthen and generalize existing results.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Xie-Bin Chen,