On 4-ordered 3-regular graphs

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

研究成果: Article同行評審

摘要

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.
原文English
頁(從 - 到)1613-1619
頁數7
期刊Mathematical and Computer Modelling
54
發行號5-6
DOIs
出版狀態Published - 九月 2011

指紋 深入研究「On 4-ordered 3-regular graphs」主題。共同形成了獨特的指紋。

引用此