We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Sufficient conditions for Hamiltonicity in multiswapped networks.

Stewart, I.A. (2016) 'Sufficient conditions for Hamiltonicity in multiswapped networks.', Journal of parallel and distributed computing., 101 . pp. 17-26.


OTIS networks are interconnection networks amenable to deployment as hybrid networks containing both electronic and optical links. Deficiencies as regards symmetry led to the subsequent formulation of biswapped networks which were later generalized to multiswapped networks so as to still enable optoelectronic implementation (as it happens, multiswapped networks also generalize previously studied hierarchical crossed cubes). Multiswapped networks of the form Msw(H;G) are known to possess good (graph-theoretic) properties as regards their use as (optoelectronic) interconnection networks (in distributed-memory multiprocessors) and in relation to those of the component networks G and H. Combinatorially they provide a hierarchical mechanism to define new networks from existing networks (so that the properties of the new network can be controlled in terms of the constituent networks). In this paper we prove that if G and H are Hamiltonian networks then the multiswapped network Msw(H;G) is also Hamiltonian. At the core of our proof is finding specially designed Hamiltonian cycles in 2-dimensional and heavily pruned 3-dimensional tori, irrespective of the actual networks G and H we happen to be working with. This lends credence to the role of tori as fundamental networks within the study of interconnection networks.

Item Type:Article
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution.
Download PDF
Publisher Web site:
Publisher statement:© 2016 The Authors. Published by Elsevier Ltd. This is an open access article under the CC-BY license (
Date accepted:22 October 2016
Date deposited:15 November 2016
Date of first online publication:09 November 2016
Date first made open access:22 November 2016

Save or Share this output

Look up in GoogleScholar