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

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.

• Shin-Shin Kao
• Hsiu-Chunj Pan

• Hamiltonian cycle
• 4-ordered
• Chordal rings
• 3-regular.

[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.