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

Říha, Stanislav

Arch. Math., Brno 24, No. 3, 137-146 (1988).

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

Citations:

Zbl 0666.05053