Optimizing Hamiltonian panconnectedness for the crossed cube architecture

Tzu-Liang Kung and Hon-Chan Chen

Applied Mathematics and Computation, 2018, vol. 331, issue C, 287-296

Abstract: A graph G of k vertices is panconnected if for any two distinct vertices x and y, it has a path of length l joining x and y for any integer l satisfying dG(x,y)≤l≤k−1, where dG(x, y) denotes the distance between x and y in G. In particular, when k ≥ 3, G is called Hamiltonian r-panconnected if for any three distinct vertices x, y, and z, there exists a Hamiltonian path P of G with dP(x,y)=l such that P(1)=x,P(l+1)=y, and P(k)=z for any integer l satisfying r≤l≤k−r−1, where P(i) denotes the ith vertex of path P for 1 ≤ i ≤ k. Then, this paper shows that the n-dimensional crossed cube, which is a popular variant of the hypercube topology, is Hamiltonian (⌈n+12⌉+1)-panconnected for n ≥ 4. The lower bound ⌈n+12⌉+1 on the path length is sharp, which is the shortest that can be embedded between any two distinct vertices with dilation 1 in the n-dimensional crossed cube.

Keywords: Hamiltonian; Panconnected; Interconnection network; Crossed cube; Path embedding (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S009630031830167X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:331:y:2018:i:c:p:287-296

DOI: 10.1016/j.amc.2018.03.002

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().