Panpositionable Hamiltonian Graphs

Abstract

A hamiltonian graph $G$ is panpositionable if for any two different vertices $x$ and $y$ of $G$ and any integer $k$ with $d_G(x,y)\le k\le |V(G)|/2$, there exists a hamiltonian cycle $C$ of $G$ with $d_C(x,y)=k$. A bipartite hamiltonian graph $G$ is bipanpositionable if for any two different vertices $x$ and $y$ of $G$ and for any integer $k$ with $d_G(x,y)\le k\le |V(G)|/2$ and $(k–d_G(x,y))$ is even, there exists a hamiltonian cycle $C$ of $G$ such that $d_C(x,y)=k$. In this paper, we prove that the hypercube $Q_n$ is bipanpositionable hamiltonian if and only if $n\ge 2$. The recursive circulant graph $G(n;1,3)$ is bipanpositionable hamiltonian if and only if $n\ge 6$ and $n$ is even; $G(n;1,2)$ is panpositionable hamiltonian if and only if $n\in \{5,6,7,8,9,11\}$, and $G(n;1,2,3)$ is panpositionable hamiltonian if and only if $n\ge 5$.