×

On graphs whose square have strong Hamiltonian properties. (English) Zbl 1210.05121

Summary: The square \(G^{2}\) of a graph \(G\) is the graph having the same vertex set as \(G\) and two vertices are adjacent if and only if they are at distance at most 2 from each other. It is known that if \(G\) has no cut-vertex, then \(G^{2}\) is Hamilton-connected (see [G. Chartrand, A. M. Hobbs, H. A. Jung, S. F. Kapoor, C. St. J. A. Nash-Williams, “The square of a block is hamiltonian connected,” J. Comb. Theory, Ser. B 16, 290–292 (1974; Zbl 0277.05129); R.J. Faudree and R.H. Schelp, The square of a block is strongly path connected, J. Comb. Theory, Ser. B 20, 47–61 (1976; Zbl 0284.05116)]). We prove that if \(G\) has only one cut-vertex, then \(G^{2}\) is Hamilton-connected. In the case that \(G\) has only two cut-vertices, we prove that if the block that contains the two cut-vertices is hamiltonian, then \(G^{2}\) is Hamilton-connected. Further, we characterize all graphs with at most one cycle having Hamilton-connected square.

MSC:

05C76 Graph operations (line graphs, products, etc.)
05C45 Eulerian and Hamiltonian graphs
05C40 Connectivity
Full Text: DOI

References:

[1] Chartrand, G.; Hobbs, A. M.; Jung, H. A.; Kapoor, S. F.; Nash-Williams, C. St. J.A., The square of a block is hamiltonian connected, J. Combin. Theory Ser. B, 16, 290-292 (1974) · Zbl 0277.05129
[2] Faudree, R. J.; Schelp, R. H., The square of a block is strongly path connected, J. Combin. Theory Ser. B, 20, 47-61 (1976) · Zbl 0284.05116
[3] Fleischner, H., The square of every two-connected graph is hamiltonian, J. Combin. Theory Ser. B, 16, 29-34 (1974) · Zbl 0256.05121
[4] Fleischner, H., In the square of graphs, Hamiltonicity and pancyclicity, hamiltonian connectedness and panconnectedness are equivalent concept, Monatsh. Math., 82, 125-149 (1976) · Zbl 0353.05043
[5] Harary, F.; Schwenk, A. J., Trees with hamiltonian square, Mathematika, 18, 138-140 (1971) · Zbl 0221.05052
[6] Hobbs, A. M., The square of a block is vertex pancyclic, J. Combin. Theory Ser. B, 20, 1-4 (1976) · Zbl 0321.05135
[7] Kronk, H. V., Is the square of every nonseperable graph hamiltonian?, Amer. Math. Monthly, 76, 1045-1046 (1969)
[8] Underground, P., On graphs with hamiltonian squares, Discrete Math., 21, 323 (1978) · Zbl 0376.05037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.