On low degree k-ordered graphs
| dc.creator | Meszaros, Karola | |
| dc.date | 2005-09-19 | |
| dc.date.accessioned | 2026-07-07T06:18:10Z | |
| dc.date.available | 2026-07-07T06:18:10Z | |
| dc.description | A simple graph G is k-ordered (respectively, k-ordered hamiltonian) if, for any sequence of k distinct vertices v_1, ..., v_k of G, there exists a cycle (respectively, a hamiltonian cycle) in G containing these k vertices in the specified order. In 1997 Ng and Schultz introduced these concepts of cycle orderability, and motivated by the fact that k-orderedness of a graph implies (k-1)-connectivity, they posed the question of the existence of low degree k-ordered hamiltonian graphs. We construct an infinite family of graphs, which we call bracelet graphs, that are (k-1)-regular and are k-ordered hamiltonian for odd k. This result provides the best possible answer to the question of the existence of low degree k-ordered hamiltonian graphs for odd k. We further show that for even k, there exist no k-ordered bracelet graphs with minimum degree k-1 and maximum degree less than k+2, and we exhibit an infinite family of bracelet graphs with minimum degree k-1 and maximum degree k+2 that are k-ordered for even k. A concept related to k-orderedness, namely that of k-edge-orderedness, is likewise strongly related to connectivity properties. We study this relation in both undirected and directed graphs, and give bounds on the connectivity necessary to imply k-(edge-)orderedness properties. | |
| dc.description | 13 pages, 0 figures | |
| dc.identifier | https://arxiv.org/abs/math/0509411 | |
| dc.identifier | http://arxiv.org/abs/math/0509411 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/94646 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C45 | |
| dc.title | On low degree k-ordered graphs | |
| dc.type | text |