## Hamiltonian lines in the square of graphs. II.(English)Zbl 0666.05054

A connected graph G is a K-graph if each block of G is a complete graph. A necessary and sufficient condition for the square of a K-graph to be Hamiltonian is proved. First, it is shown that for each K-graph G there is a corresponding cactus C with the same vertices as G as well as the same block structure such that $$G^ 2$$ is Hamiltonian if and only if $$C^ 2$$ is Hamiltonian. Then using a forbidden structure characterization of those cacti C for which $$C^ 2$$ is Hamiltonian [see the author, Hamiltonian lines in the square of graphs, ibid., No.2, 45-56 (1988; see above)], a corresponding characterization is given for the square of a K-graph to be Hamiltonian.
Reviewer: R.Faudree

### MSC:

 05C45 Eulerian and Hamiltonian graphs

Zbl 0666.05053
Full Text: