Bipanconnectivity and bipancyclicity in k-ary n-cubes

Stewart, I.A.; Xiang, Y.

Abstract

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 Q_n^k is bipanconnected and edge-bipancyclic, when k ≥ 3 and n ≥ 2, and we also show that when k is odd, Q_n^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 Q_n^k, even in the presence of a faulty processor.

Citation

Stewart, I., & Xiang, Y. (2009). Bipanconnectivity and bipancyclicity in k-ary n-cubes. IEEE Transactions on Parallel and Distributed Systems, 20(1), 25-33. https://doi.org/10.1109/tpds.2008.45

• Journal Article Type: Article
• Publication Date: Jan 1, 2009
• Deposit Date: Jun 9, 2009
• Publicly Available Date: Jun 24, 2009
• Journal: IEEE Transactions on Parallel and Distributed Systems
• Print ISSN: 1045-9219
• Electronic ISSN: 1558-2183
• Publisher: Institute of Electrical and Electronics Engineers
• Peer Reviewed: Peer Reviewed
• Volume: 20
• Issue: 1
• Pages: 25-33
• DOI: https://doi.org/10.1109/tpds.2008.45
• Keywords: Interconnection networks, k-ary n-cubes, Bipanconnectivity, Bipancyclicity.
• Public URL: https://durham-repository.worktribe.com/output/1554512
• Publisher URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=4694808&arnumber=4479449&count=12&index=2