Journal of Combinatorics
Volume 9 (2018)
A hamilton cycle in which specified vertices are located in polar opposite
Pages: 35 – 56
Enomoto conjectured that if a graph $G$ of order $n$ has minimum degree at least $n / 2 + 1$, then for any two vertices $x$ and $y$, there is a hamilton cycle $C$ such that $d_C (x, y) = \lfloor n/2 \rfloor$. In this paper, we show the existence of a hamilton cycle $C$ in $G$ such that $d_C (x, y) \geq (n-4)/3$.
hamilton cycle, Dirac condition, hamilton connectedness, panconnectivity
2010 Mathematics Subject Classification
The second author’s work was supported by JSPS KAKENHI Grant Number 26400190.
Received 5 February 2015
Published 5 January 2018