  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.
