Mathematics – Combinatorics
Scientific paper
2005-09-19
Mathematics
Combinatorics
13 pages, 0 figures
Scientific paper
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.
No associations
LandOfFree
On low degree k-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 low degree k-ordered graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On low degree k-ordered graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-298308