Embedding Two Edge-Disjoint Hamiltonian Cycles into Parity Cubes

Yan Wang; Jian Xi Fan; Wen Jun Liu; Xi Wang

doi:10.4028/www.scientific.net/AMM.336-338.2248

Paper Titles

The Study and Realization of Customer-Churn Model Based on Date Mining in Telcom
p.2229

Exponential Decay of Global Solutions for some Quasilinear Higher-Order Wave Equation
p.2233

Two Partitioning Algorithms for Generating of M Sets of the Frieze Group
p.2238

Embedding Two Edge-Disjoint Hamiltonian Cycles into Parity Cubes
p.2248

Study of an Improved Petri Net Model for Scheduling of DEDS
p.2252

Frequency Hopping Prediction Based on Multi-Kernel SVM
p.2256

Calculation of Cosmic Radiation Exposure on Flights with Computer Program
p.2261

Solutions for a Class of the Higher Diophantine Equation
p.2265

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 336-338Embedding Two Edge-Disjoint Hamiltonian Cycles...

Embedding Two Edge-Disjoint Hamiltonian Cycles into Parity Cubes

Abstract:

Edge-disjoint Hamiltonian cycles are helpful to implement efficient and fault tolerant algorithms that require a ring structure. The n-dimensional parity cube, PQn, is a variant of hypercube. The existence of two edge-disjoint Hamiltonian cycles in parity cube is unknown. In this paper, we prove that there exist two edge-disjoint Hamiltonian cycles in n-dimensional parity cube with n≥4.

You might also be interested in these eBooks

Industrial Instrumentation and Control Systems II

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 336-338)

Pages:

2248-2251

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.336-338.2248

Citation:

Cite this paper

Online since:

July 2013

Authors:

Yan Wang, Jian Xi Fan, Wen Jun Liu, Xi Wang

Keywords:

Edge-Disjoint Hamiltonian Cycles, Embedding, Interconnection Networks, Parity Cubes

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] Hung, R. -W., Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes. Theoretical Computer Science, 2011. 412(35): pp.4747-4753.

DOI: 10.1016/j.tcs.2011.05.004

Google Scholar

[2] Lee, S. and K. Shin, Interleaved all-to-all reliable broadcast on meshes and hypercubes. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1994. 5(5): pp.449-458.

DOI: 10.1109/71.282556

Google Scholar

[3] Rowley, R. and B. Bose. Edge-disjoint Hamiltonian cycles in de Bruijn networks. in Proceedings of Distributed Memory Computing Conference. 1991. IEEE.

DOI: 10.1109/dmcc.1991.633359

Google Scholar

[4] Micheneau, C., Disjoint Hamiltonian cycles in recursive circulant graphs. Information Processing Letters, 1997. 61(5): pp.259-264.

DOI: 10.1016/s0020-0190(97)00020-3

Google Scholar

[5] Ferrara, M., R. Gould, G. Tansey, and T. Whalen, Disjoint hamiltonian cycles in bipartite graphs. Discrete Mathematics, 2009. 309(12): pp.3811-3820.

DOI: 10.1016/j.disc.2008.10.026

Google Scholar

[6] Wang, D. and L. Zhao, The twisted-cube connected networks. Journal of Computer Science and Technology, 1999. 14(2): pp.181-187.

Google Scholar

[7] Park, J.H., H.C. Kim, and H.S. Lim. Fault-hamiltonicity of hypercube-like interconnection networks. in Proceedings of 19th IEEE International Parallel and Distributed Processing Symposium. 2005. IEEE.

DOI: 10.1109/ipdps.2005.223

Google Scholar

[8] Park, C.D. and K.Y. Chwa, Hamiltonian properties on the class of hypercube-like networks. Information Processing Letters, 2004. 91(1): pp.11-17.

DOI: 10.1016/j.ipl.2004.03.009

Google Scholar

[9] Wang, X., J. Fan, X. Jia, S. Zhang, and J. Yu, Embedding meshes into twisted-cubes. Information Sciences, 2011. 181(14): pp.3085-3099.

DOI: 10.1016/j.ins.2011.02.019

Google Scholar

[10] Wang, Y., J. Fan, and Y. Han. Construction of independent spanning trees on twisted-cubes. in 2011 IEEE International Conference on Computer Science and Automation Engineering (CSAE). 2011. IEEE.

DOI: 10.1109/csae.2011.5952464

Google Scholar

[11] Wang, Y., J. Fan, and X. Jia, An algorithm to construct independent spanning trees on parity cubes. Theoretical Computer Science, 2012. 465(21): pp.61-72.

DOI: 10.1016/j.tcs.2012.08.020

Google Scholar