| Abstract: | This paper deals with the problem of characterizing the pairs of vertices x,y in a connected graph G such that G3 - {x,y} is hamiltonian, where G3 is the cube of G. It is known that the cube G3 is 2-hamiltonian if G is 2-connected. In this paper, we first prove the stronger result that G3 - {x,y} is hamiltonian if either x or y is not a cut-vertex of G, and then proceed to characterize those cut-vertices x and y of G such that G3 -{x,y} is hamiltonian. As a simple consequence of these, we obtain Schaar's characterization of a connected graph G such that G3 is 2-hamiltonian. |
