On 4-ordered 3-regular graphs

A graph GG is kk-ordered   if for any sequence of kk distinct vertices v1,v2,…,vkv1,v2,…,vk of GG there exists a cycle in GG containing these kk 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 K4K4 and the complete bipartite graph K3,3K3,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 nn with n≥8n≥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 K4K4 and the Petersen graph. In this paper, we prove that there exists a bipartite non-vertex-transitive 4-ordered 3-regular graph of order nn for any sufficiently large even integer nn. Moreover, there exists a non-bipartite non-vertex-transitive 4-ordered 3-regular graph of order nn for any sufficiently large even integer nn.