On $k$-ordered Hamiltonian Graphs

Details On $k$-ordered Hamiltonian Graphs On $k$-ordered Hamiltonian Graphs

1996-12-04

arxiv.org/abs/math/9612212v1

Mathematics

Combinatorics

Scientific paper

A Hamiltonian graph $G$ of order $n$ is $k$-ordered, $2\leq k \leq n$, if for every sequence $v_1, v_2, \ldots ,v_k$ of $k$ distinct vertices of $G$, there exists a Hamiltonian cycle that encounters $v_1, v_2, \ldots , v_k$ in this order. In this paper, answering a question of Ng and Schultz, we give a sharp bound for the minimum degree guaranteeing that a graph is a $k$-ordered Hamiltonian graph under some mild restrictions. More precisely, we show that there are $\varepsilon, n_0> 0$ such that if $G$ is a graph of order $n\geq n_0$ with minimum degree at least $\lceil \frac{n}{2} \rceil + \lfloor \frac{k}{2} \rfloor - 1$ and $2\leq k \leq \eps n$, then $G$ is a $k$-ordered Hamiltonian graph. It is also shown that this bound is sharp for every $2\leq k \leq \lfloor \frac{n}{2} \rfloor$.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-469551