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) \leq k \leq |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) \leq k \leq |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 \geq 2\). The recursive circulant graph \(G(n;1,3)\) is bipanpositionable hamiltonian if and only if \(n \geq 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 \geq 5\).