Mathematics – Combinatorics
Scientific paper
2005-09-19
Mathematics
Combinatorics
15 pages, 10 figures
Scientific paper
A simple graph $G$ is \textit{k-ordered} (respectively, \textit{k-ordered hamiltonian}), if for any sequence of $k$ distinct vertices $v_1, ..., v_k$ of $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 $K_4$ and $K_{3, 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 $K_4$ and $K_{3, 3}$ that is 3-regular 4-ordered hamiltonian is the Heawood graph, and we exhibit forbidden subgraphs for 3-regular 4-ordered hamiltonian graphs on more than 10 vertices. Finally, we construct an infinite family of 3-regular 4-ordered graphs.
No associations
LandOfFree
On 3-regular 4-ordered graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On 3-regular 4-ordered graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On 3-regular 4-ordered graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-298313