摘要
Abstract A graph g is k-ordered Hamiltonian, 2 h k h n, if for every ordered sequence S of k distinct vertices of G, there exists a Hamiltonian cycle that encounters S in the given order. In this article, we prove that if G is a graph on n vertices with degree sum of nonadjacent vertices at least $n+{{3k - 9} \over 2}$, then G is k-ordered Hamiltonian for k=3,4,...,￠${n \over {19}}$?. We also show that the degree sum bound can be reduced to n+ 2 ￠ ${k \over {2}}$ m 2 if $\kappa(G)\ge {{3k - 1} \over 2}$ or '(G) S 5k m 4. Several known results are generalized.
Abstract A graph g is k-ordered Hamiltonian, 2 h k h n, if for every ordered sequence S of k distinct vertices of G, there exists a Hamiltonian cycle that encounters S in the given order. In this article, we prove that if G is a graph on n vertices with degree sum of nonadjacent vertices at least $n+{{3k - 9} \over 2}$, then G is k-ordered Hamiltonian for k=3,4,...,￠${n \over {19}}$?. We also show that the degree sum bound can be reduced to n+ 2 ￠ ${k \over {2}}$ m 2 if $\kappa(G)\ge {{3k - 1} \over 2}$ or '(G) S 5k m 4. Several known results are generalized.
基金
Partially supported by the National Natural Sciences Foundation of China (No.19831080).
