Graph powers and k-ordered Hamiltonicity

Details Graph powers and k-ordered Hamiltonicity Graph powers and k-ordered Hamiltonicity

2003-07-28

arxiv.org/abs/math/0307359v1

Mathematics

Combinatorics

18 pages, 8 figures; submitted to J. Graph Theory

Scientific paper

It is known that if G is a connected simple graph, then G^3 is Hamiltonian (in fact, Hamilton-connected). A simple graph is k-ordered Hamiltonian if for any sequence v_1, v_2, ..., v_k of k vertices there is a Hamiltonian cycle containing these vertices in the given order. In this paper, we prove that G^(3k/2 + 1) is k-ordered Hamiltonian for a connected graph G on at least k vertices. We further show that if G is connected, then G^4 is 4-ordered Hamiltonian and that if G is Hamiltonian, then G^3 is 5-ordered Hamiltonian. We also give bounds on the smallest power p_k such that G^p_k is k-ordered Hamiltonian for G=P_n and G=C_n.

Affiliated with

Also associated with

No associations

Rating

Graph powers and k-ordered Hamiltonicity 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 Graph powers and k-ordered Hamiltonicity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph powers and k-ordered Hamiltonicity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-108091