Skip to main content

Research Repository

Advanced Search

Bipanconnectivity and bipancyclicity in k-ary n-cubes

Stewart, I.A.; Xiang, Y.

Bipanconnectivity and bipancyclicity in k-ary n-cubes Thumbnail


Y. Xiang


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.


Stewart, I., & Xiang, Y. (2009). Bipanconnectivity and bipancyclicity in k-ary n-cubes. IEEE Transactions on Parallel and Distributed Systems, 20(1), 25-33.

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
Publisher Institute of Electrical and Electronics Engineers
Peer Reviewed Peer Reviewed
Volume 20
Issue 1
Pages 25-33
Keywords Interconnection networks, k-ary n-cubes, Bipanconnectivity, Bipancyclicity.
Publisher URL


Published Journal Article (1.4 Mb)

Copyright Statement
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author&#039;s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.<br /> <br /> &copy;2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

You might also like

Downloadable Citations