標題: On 4-ordered 3-regular graphs
作者: Tsai, Ming
Tsai, Tsung-Han
Tan, Jimmy J. M.
Hsu, Lih-Hsing
資訊工程學系
Department of Computer Science
關鍵字: k-ordered;Cubic graphs
公開日期: 1-九月-2011
摘要: 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.
URI: http://dx.doi.org/10.1016/j.mcm.2011.04.034
http://hdl.handle.net/11536/20069
ISSN: 0895-7177
DOI: 10.1016/j.mcm.2011.04.034
期刊: MATHEMATICAL AND COMPUTER MODELLING
Volume: 54
Issue: 5-6
起始頁: 1613
結束頁: 1619
顯示於類別:期刊論文


文件中的檔案:

  1. 000291243300036.pdf