{"title":"A Further Study on the 4-Ordered Property of Some Chordal Ring Networks","authors":"Shin-Shin Kao, Hsiu-Chunj Pan","volume":97,"journal":"International Journal of Mathematical and Computational Sciences","pagesStart":59,"pagesEnd":63,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/10000360","abstract":"
Given a graph G. A cycle of G is a sequence of
\r\nvertices of G such that the first and the last vertices are the same.
\r\nA hamiltonian cycle of G is a cycle containing all vertices of G.
\r\nThe graph G is k-ordered (resp. k-ordered hamiltonian) if for any
\r\nsequence of k distinct vertices of G, there exists a cycle (resp.
\r\nhamiltonian cycle) in G containing these k vertices in the specified
\r\norder. Obviously, any cycle in a graph is 1-ordered, 2-ordered and 3-
\r\nordered. Thus the study of any graph being k-ordered (resp. k-ordered
\r\nhamiltonian) always starts with k = 4. Most studies about this topic
\r\nwork on graphs with no real applications. To our knowledge, the
\r\nchordal ring families were the first one utilized as the underlying
\r\ntopology in interconnection networks and shown to be 4-ordered.
\r\nFurthermore, based on our computer experimental results, it was
\r\nconjectured that some of them are 4-ordered hamiltonian. In this
\r\npaper, we intend to give some possible directions in proving the
\r\nconjecture.<\/p>\r\n","references":"[1] S. S. Kao, S. C. Wey and H. C. Pan, The 4-ordered property of\r\nsome chordal ring networks, Mathematics Methods in Engineering and\r\nEconomics, Proceedings of the 2014 International Conference on Applied\r\nMathematics and Computational Methods in Engineering, ISBN: 978-1-\r\n61804-230-9, 2014, pp. 44\u201348.\r\n[2] Lenhard Ng and Michelle Schultz, k-ordered hamiltonian graphs, Journal\r\nof Graph Theory, 24, 1997, No. 1, pp. 45\u201357.\r\n[3] Ralph J. Faudree, Survey of results on k-ordered graphs, Discrete Mathematics,\r\n229, 2001, pp. 73\u201387.\r\n[4] Ruijuan Li, Shengjia Li, and Yubao Guo, Degree conditions on distance 2\r\nvertices that imply k-ordered hamiltonian, Discrete Applied Mathematics,\r\n158, 2010, pp. 331\u2013339.\r\n[5] Karola Meszaros, On 3-regular 4-ordered graphs, Discrete Mathematics,\r\n308, 2008, pp. 2149\u20132155.\r\n[6] Lih-Hsing Hsu, Jimmy J.M. Tan, Eddie Cheng, Laszlo Liptak, Cheng-\r\nKuan Lin, and Ming Tsai, Solution to an open problem on 4-ordered\r\nHamiltonian graphs, Discrete Mathematics, 312, 2012, pp. 2356\u20132370.\r\n[7] Chun-Nan Hung, David Lu, Randy Jia, Cheng-Kuan Lin, Laszlo Liptak,\r\nEddie Cheng, Jimmy J.M. Tan, and Lih-Hsing Hsu, 4-ordered-\r\nHamiltonian problems of the generalized Petersen graph GP(n,4), Mathematical\r\nand Computer Modelling 57, 2013, pp. 595\u2013601.\r\n[8] R.N. Farah, M.Othman, and M.H. Selamat, Combinatorial properties of\r\nmodified chordal rings degree four networks, Journal of Computer Science\r\n6, 3, 2010, pp. 279\u2013284.\r\n[9] Xianbing Wang and Yong Meng Teo, Global data computation in chordal\r\nrings, J. Parallel and Distributed Computing, 69, 2009, pp. 725\u2013736. ","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 97, 2015"}