Hamiltonicity in squares of graphs revisited

Herbert Fleischner

Abstract

The study of powers of graphs was initiated by Milan Sekanina (Brno) in the late 1950s. The cube of a graph was readily shown to be hamiltonian. This was not so easy for the squares of graphs. In the 1970s, quite a few papers on hamiltonicity and hamiltonian connectedness in squares of graphs were published; even a polynomial time algorithm for finding a hamiltonian cycle in the square of a 2-connected graph (block, for short) was developed. For some of the central results on hamiltonian cycles in the square of a block, short proofs were found in the 1990s and later. In more recent developments best possible results on hamiltonicity/hamiltonian connectedness in the square of a block were established by the speaker and Gek Ling Chia (Kuala Lumpur), Jan Ekstein and Jan Brousek (Plzen) respectively. These results will serve as the basis for describing the most general structure for a graph to be hamiltonian/hamiltonian