On 4-ordered 3-regular graphs

Abstract

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.