On 3-regular 4-ordered graphs
On 3-regular 4-ordered graphs
复制标题
在 3-正则 4-有序图上
DOI：
10.1016/j.disc.2007.04.061
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Karola Mészáros
中科院分区：
文献类型：
--
作者：
Karola Mészáros
一个简单图G是k-序的(分别是k-序的哈密顿量)，如果对任何k个不同的顶点序列v1，…在G中存在一个圈(分别称为哈密顿圈)，它以指定的顺序包含这k个顶点。1997年，Ng和Schultz引入了圈可序的概念，并提出了除K4和K3之外的3-正则4-序(哈密尔顿)图的存在性问题。证明了具有6个以上顶点的3-正则4-序图G是无平方的，并且证明了最小的三角形无平方图，即Petersen图是4-序的。此外，我们还证明了K4和K3，3之后的最小图即3-正则4-序哈密尔顿图是Heawood图。最后，我们构造了一个3-正则4-序图的无限族。
A simple graph G is k-ordered (respectively, k-ordered hamiltonian), if for any sequence of k distinct vertices v1,…,vkof G there exists a cycle (respectively, hamiltonian cycle) in G containing these k vertices in the specified order. In 1997 Ng and Schultz introduced these concepts of cycle orderability and posed the question of the existence of 3-regular 4-ordered (hamiltonian) graphs other than K4and K3,3. Ng and Schultz observed that a 3-regular 4-ordered graph on more than 4 vertices is triangle free. We prove that a 3-regular 4-ordered graph G on more than 6 vertices is square free,and we show that the smallest graph that is triangle and square free, namely the Petersen graph, is 4-ordered. Furthermore, we prove that the smallest graph after K4and K3,3that is 3-regular 4-ordered hamiltonianis the Heawood graph. Finally, we construct an infinite family of 3-regular 4-ordered graphs.