On 3-regular 4-ordered graphs |
| |
Authors: | Karola Mé szá ros |
| |
Affiliation: | Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA |
| |
Abstract: | 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 K4 and 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 K4 and K3,3 that is 3-regular 4-ordered hamiltonianis the Heawood graph. Finally, we construct an infinite family of 3-regular 4-ordered graphs. |
| |
Keywords: | k-ordered graph k-ordered hamiltonian 3-Regular 4-ordered |
本文献已被 ScienceDirect 等数据库收录! |
|