On 4-ordered 3-regular graphs

Ming Tsai, Tsung Han Tsai, Jiann-Mean Tan, Lih Hsing Hsu

Research output: Contribution to journalArticlepeer-review

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,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.
Original languageEnglish
Pages (from-to)1613-1619
Number of pages7
JournalMathematical and Computer Modelling
Volume54
Issue number5-6
DOIs
StatePublished - Sep 2011

Keywords

  • k-ordered; Cubic graphs

Fingerprint Dive into the research topics of 'On 4-ordered 3-regular graphs'. Together they form a unique fingerprint.

Cite this