Given a 2-connected graph G on n vertices, let G* be its partially square graph, obtained by adding edges uv whenever the vertices u,v have a common neighbor x satisfying the condition , where . In particular, this condition is satisfied if x does not center a claw (an induced ). Clearly G ⊆ G* ⊆ G², where G² is the square of G. For any independent triple X = x,y,z we define σ̅(X) = d(x) + d(y) + d(z) - |N(x) ∩ N(y) ∩ N(z)|. Flandrin et al. proved that a 2-connected graph G is hamiltonian if [σ̅]₃(X) ≥ n holds for any independent triple X in G. Replacing X in G by X in the larger graph G*, Wu et al. improved recently this result. In this paper we characterize the nonhamiltonian 2-connected graphs G satisfying the condition [σ̅]₃(X) ≥ n-1 where X is independent in G*. Using the concept of dual closure we (i) give a short proof of the above results and (ii) we show that each graph G satisfying this condition is hamiltonian if and only if its dual closure does not belong to two well defined exceptional classes of graphs. This implies that it takes a polynomial time to check the nonhamiltonicity or the hamiltonicity of such G.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1357,
author = {Ahmed Ainouche and Serge Lapiquonne},
title = {Variations on a sufficient condition for Hamiltonian graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {27},
year = {2007},
pages = {229-240},
zbl = {1135.05031},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1357}
}
Ahmed Ainouche; Serge Lapiquonne. Variations on a sufficient condition for Hamiltonian graphs. Discussiones Mathematicae Graph Theory, Tome 27 (2007) pp. 229-240. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1357/
[000] [1] A. Ainouche and N. Christofides, Semi-independence number of a graph and the existence of hamiltonian circuits, Discrete Applied Math. 17 (1987) 213-221, doi: 10.1016/0166-218X(87)90025-4.
[001] [2] A. Ainouche, An improvement of Fraisse's sufficient condition for hamiltonian graphs, J. Graph Theory 16 (1992) 529-543, doi: 10.1002/jgt.3190160602. | Zbl 0770.05070
[002] [3] A. Ainouche, O. Favaron and H. Li, Global insertion and hamiltonicity in DCT-graphs, Discrete Math. 184 (1998) 1-13, doi: 10.1016/S0012-365X(97)00157-X. | Zbl 0958.05084
[003] [4] A. Ainouche and M. Kouider, Hamiltonism and Partially Square Graphs, Graphs and Combinatorics 15 (1999) 257-265, doi: 10.1007/s003730050059. | Zbl 0933.05096
[004] [5] A. Ainouche and I. Schiermeyer, 0-dual closures for several classes of graphs, Graphs and Combinatorics 19 (2003) 297-307, doi: 10.1007/s00373-002-0523-y.
[005] [6] A. Ainouche, Extension of several sufficient conditions for hamiltonian graphs, Discuss. Math. Graph Theory 26 (2006) 23-39, doi: 10.7151/dmgt.1298.
[006] [7] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, London, 1976.) | Zbl 1226.05083
[007] [8] J.A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111-135, doi: 10.1016/0012-365X(76)90078-9. | Zbl 0331.05138
[008] [9] E. Flandrin, H.A. Jung and H. Li, Hamiltonism, degrees sums and neighborhood intersections, Discrete Math. 90 (1991) 41-52, doi: 10.1016/0012-365X(91)90094-I. | Zbl 0746.05038
[009] [10] Z. Wu, X. Zhang and X. Zhou, Hamiltonicity, neighborhood intersections and the partially square graphs, Discrete Math. 242 (2002) 245-254, doi: 10.1016/S0012-365X(00)00394-0. | Zbl 0995.05085