A Further Study on the 4-Ordered Property of Some Chordal Ring Networks

Authors: Shin-Shin Kao, Hsiu-Chunj Pan

Abstract:

Given a graph G. A cycle of G is a sequence of vertices of G such that the first and the last vertices are the same. A hamiltonian cycle of G is a cycle containing all vertices of G. The graph G is k-ordered (resp. k-ordered hamiltonian) if for any sequence of k distinct vertices of G, there exists a cycle (resp. hamiltonian cycle) in G containing these k vertices in the specified order. Obviously, any cycle in a graph is 1-ordered, 2-ordered and 3- ordered. Thus the study of any graph being k-ordered (resp. k-ordered hamiltonian) always starts with k = 4. Most studies about this topic work on graphs with no real applications. To our knowledge, the chordal ring families were the first one utilized as the underlying topology in interconnection networks and shown to be 4-ordered. Furthermore, based on our computer experimental results, it was conjectured that some of them are 4-ordered hamiltonian. In this paper, we intend to give some possible directions in proving the conjecture.

Keywords: Hamiltonian cycle, 4-ordered, Chordal rings, 3-regular.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1098948

References:

[1] S. S. Kao, S. C. Wey and H. C. Pan, The 4-ordered property of some chordal ring networks, Mathematics Methods in Engineering and Economics, Proceedings of the 2014 International Conference on Applied Mathematics and Computational Methods in Engineering, ISBN: 978-1- 61804-230-9, 2014, pp. 44–48.
[2] Lenhard Ng and Michelle Schultz, k-ordered hamiltonian graphs, Journal of Graph Theory, 24, 1997, No. 1, pp. 45–57.
[3] Ralph J. Faudree, Survey of results on k-ordered graphs, Discrete Mathematics, 229, 2001, pp. 73–87.
[4] Ruijuan Li, Shengjia Li, and Yubao Guo, Degree conditions on distance 2 vertices that imply k-ordered hamiltonian, Discrete Applied Mathematics, 158, 2010, pp. 331–339.
[5] Karola Meszaros, On 3-regular 4-ordered graphs, Discrete Mathematics, 308, 2008, pp. 2149–2155.
[6] Lih-Hsing Hsu, Jimmy J.M. Tan, Eddie Cheng, Laszlo Liptak, Cheng- Kuan Lin, and Ming Tsai, Solution to an open problem on 4-ordered Hamiltonian graphs, Discrete Mathematics, 312, 2012, pp. 2356–2370.
[7] Chun-Nan Hung, David Lu, Randy Jia, Cheng-Kuan Lin, Laszlo Liptak, Eddie Cheng, Jimmy J.M. Tan, and Lih-Hsing Hsu, 4-ordered- Hamiltonian problems of the generalized Petersen graph GP(n,4), Mathematical and Computer Modelling 57, 2013, pp. 595–601.
[8] R.N. Farah, M.Othman, and M.H. Selamat, Combinatorial properties of modified chordal rings degree four networks, Journal of Computer Science 6, 3, 2010, pp. 279–284.
[9] Xianbing Wang and Yong Meng Teo, Global data computation in chordal rings, J. Parallel and Distributed Computing, 69, 2009, pp. 725–736.