TY - JOUR

T1 - On 4-ordered 3-regular graphs

AU - Tsai, Ming

AU - Tsai, Tsung Han

AU - Tan, Jiann-Mean

AU - Hsu, Lih Hsing

PY - 2011/9

Y1 - 2011/9

N2 - 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,K-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.

AB - 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,K-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.

KW - k-ordered; Cubic graphs

U2 - 10.1016/j.mcm.2011.04.034

DO - 10.1016/j.mcm.2011.04.034

M3 - Article

VL - 54

SP - 1613

EP - 1619

JO - Mathematical and Computer Modelling

JF - Mathematical and Computer Modelling

SN - 0895-7177

IS - 5-6

ER -