Premium
The 2‐hamiltonian cubes of graphs
Author(s) -
Koh K. M.,
Teo K. L.
Publication year - 1989
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190130609
Subject(s) - combinatorics , mathematics , hamiltonian (control theory) , vertex (graph theory) , hamiltonian path , graph , simple graph , pancyclic graph , connectivity , discrete mathematics , line graph , pathwidth , mathematical optimization
This paper deals with the problem of characterizing the pairs of vertices x,y in a connected graph G such that G 3 ‐ { x,y } is hamiltonian, where G 3 is the cube of G. It is known that the cube G 3 is 2‐hamiltonian if G is 2‐connected. In this paper, we first prove the stronger result that G 3 ‐ { 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 G 3 ‐{ x,y } is hamiltonian. As a simple consequence of these, we obtain Schaar's characterization of a connected graph G such that G 3 is 2‐hamiltonian.