On 3-regular 4-ordered graphs
| dc.creator | Meszaros, Karola | |
| dc.date | 2005-09-19 | |
| dc.date.accessioned | 2026-07-07T06:18:11Z | |
| dc.date.available | 2026-07-07T06:18:11Z | |
| dc.description | 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. | |
| dc.description | 15 pages, 10 figures | |
| dc.identifier | https://arxiv.org/abs/math/0509413 | |
| dc.identifier | http://arxiv.org/abs/math/0509413 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/94648 | |
| dc.subject | Combinatorics | |
| dc.title | On 3-regular 4-ordered graphs | |
| dc.type | text |