A hamilton cycle in which specified vertices are located in polar opposite

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$.

Keywords

hamilton cycle, Dirac condition, hamilton connectedness, panconnectivity

2010 Mathematics Subject Classification

05C45

Full Text (PDF format)

The second author’s work was supported by JSPS KAKENHI Grant Number 26400190.

Received 5 February 2015

Published 5 January 2018