Journal of Combinatorics

Volume 9 (2018)

Number 1

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

Pages: 35 – 56

DOI: https://dx.doi.org/10.4310/JOC.2018.v9.n1.a4

Authors

Hui Du

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

Abstract

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

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

Received 5 February 2015

Published 5 January 2018