Improving the panconnectedness property of locally twisted cubes

Abstract

The n-dimensional locally twisted cube LTQ_n is a promising alternative to the hypercube because of its great properties. Not only is LTQ_n n-connected, but also meshes, torus, and edge-disjoint Hamiltonian cycles can embed in it. Ma and Xu [Panconnectivity of locally twisted cubes, Appl. Math. Lett. 19 (2006), pp. 681–685] investigated the panconnectivity of LTQ_n for flexible routing. In this paper, we combine panconnectivity with Hamiltonian connectedness to define Hamiltonian r-panconnectedness: a graph G of m vertices, m≥3, is Hamiltonian r-panconnected if for any three distinct vertices x, y, and z of G there exists a Hamiltonian path P of G such that P(1)=x, P(l+1)=y, and P(m)=z for every r≤l≤m−1−r, where P(i) denotes the ith vertex of P for 1≤i≤m. Then, we show that LTQ_n is Hamiltonian n-panconnected for n≥5. This property admits the path embedding via an intermediate node at any prescribed position, and our result achieves an improvement over that of Ma and Xu.

Keywords:

• Hamiltonian
• panconnected
• interconnection network
• locally twisted cube

2010 AMS Subject Classifications:

• 05C38
• 68R10
• 90B10

Acknowledgements

We would like to express the most immense gratitude to the anonymous referees and the editor for their reviews and comments. They greatly improve the quality of this paper. This work is supported in part by the National Science Council of the Republic of China under Contracts NSC 100-2221-E-167-018 and NSC 102-2221-E-468-018.