17-09-2009, 02:53 AM
Bipanconnectivity and Bipancyclicity in k-ary n-cubes
In this paper we give precise solutions to problems posed by Wang, an, Pan, Wang and Qu and by Hsieh, Lin and Huang. In particular, we show that Qn k is bipanconnected and edge-bipancyclic, when k ges 3 and n ges 2, and we also show that when k is odd, Qn k is m-panconnected, for m= (n (k-1) +2k-6)/2, and (k-1)-pancyclic (these bounds are optimal).
We introduce a path-shortening technique, called progressive shortening, and strengthen existing results,
Showing that when paths are formed using progressive shortening then these paths can be efficiently constructed and used to solve a problem relating to the distributed simulation of linear arrays and cycles in a parallel machine whose interconnection network is Qn k, even in the presence of a faulty processor.