Journal of Combinatorics

Volume 9 (2018)

Number 1

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

Pages: 35 – 56



Hui Du

Kiyoshi Yoshimoto (Department of Mathematics, College of Science and Technology, Nihon University, Tokyo, Japan)


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