Browsing by Author "Tsai, Ming"

Now showing 1 - 2 of 2

On 4-ordered 3-regular graphs
(2011-09-01)
Tsai, Ming
;
Tsai, Tsung-Han
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
;
資訊工程學系
A graph G is k-ordered if for any sequence of k distinct vertices nu(1), nu(2), ..., nu(k) of G there exists a cycle in G containing these k vertices in the specified order. In 1997, Ng and Schultz posed the question of the existence of 4-ordered 3-regular graphs other than the complete graph K(4) and the complete bipartite graph K(3,3). In 2008, Meszaros solved the question by proving that the Petersen graph and the Heawood graph are 4-ordered 3-regular graphs. Moreover, the generalized Honeycomb torus GHT(3, n, 1) is 4-ordered for any even integer n with n >= 8. Up to now, all the known 4-ordered 3-regular graphs are vertex transitive. Among these graphs, there are only two non-bipartite graphs, namely the complete graph K(4) and the Petersen graph. In this paper, we prove that there exists a bipartite non-vertex-transitive 4-ordered 3-regular graph of order n for any sufficiently large even integer n. Moreover, there exists a non-bipartite non-vertex-transitive 4-ordered 3-regular graph of order n for any sufficiently large even integer n. (C) 2011 Elsevier Ltd. All rights reserved.
Solution to an open problem on 4-ordered Hamiltonian graphs
(2012-08-06)
Hsu, Lih-Hsing
;
Tan, Jimmy J. M.
;
Cheng, Eddie
;
Liptak, Laszlo
;
Lin, Cheng-Kuan
A graph G is k-ordered if for any sequence of k distinct vertices of G, there exists a cycle in G containing these k vertices in the specified order. It is k-ordered Hamiltonian if, in addition, the required cycle is Hamiltonian. The question of the existence of an infinite class of 3-regular 4-ordered Hamiltonian graphs was posed in Ng and Schultz (1997) [10]. At the time, the only known examples were K-4 and K-3.3. Some progress was made in Meszaros (2008) [9] when the Peterson graph was found to be 4-ordered and the Heawood graph was proved to be 4-ordered Hamiltonian: moreover an infinite class of 3-regular 4-ordered graphs was found. In this paper we show that a subclass of generalized Petersen graphs are 4-ordered and give a complete classification for which of these graphs are 4-ordered Hamiltonian. In particular, this answers the open question regarding the existence of an infinite class of 3-regular 4-ordered Hamiltonian graphs. Moreover, a number of results related to other open problems are presented. (C) 2012 Elsevier B.V. All rights reserved.