Discussiones Mathematicae Graph Theory 27(2) (2007)
229240
doi: 10.7151/dmgt.1357
Ahmed Ainouche and Serge Lapiquonne
UAG  CEREGMIA  GRIMAAG
B.P. 7209, 97275 Schoelcher Cedex, Martinique FRANCE
email: a.ainouche@martinique.univag.fr
email: s.lapiquonne@martinique.univag.fr

Flandrin et al. proved that a 2connected graph G is hamiltonian if [`(σ)]_{3}(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 2connected graphs G satisfying the condition [`(σ)] _{3}(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.
Keywords: cycles, partially square graph, degree sum, independent sets, neighborhood unions and intersections, dual closure.
2000 Mathematics Subject Classification: 05C38, 05C45.
[1]  A. Ainouche and N. Christofides, Semiindependence number of a graph and the existence of hamiltonian circuits, Discrete Applied Math. 17 (1987) 213221, doi: 10.1016/0166218X(87)900254. 
[2]  A. Ainouche, An improvement of Fraisse's sufficient condition for hamiltonian graphs, J. Graph Theory 16 (1992) 529543, doi: 10.1002/jgt.3190160602. 
[3]  A. Ainouche, O. Favaron and H. Li, Global insertion and hamiltonicity in DCTgraphs, Discrete Math. 184 (1998) 113, doi: 10.1016/S0012365X(97)00157X. 
[4]  A. Ainouche and M. Kouider, Hamiltonism and Partially Square Graphs, Graphs and Combinatorics 15 (1999) 257265, doi: 10.1007/s003730050059. 
[5]  A. Ainouche and I. Schiermeyer, 0dual closures for several classes of graphs, Graphs and Combinatorics 19 (2003) 297307, doi: 10.1007/s003730020523y. 
[6]  A. Ainouche, Extension of several sufficient conditions for hamiltonian graphs, Discuss. Math. Graph Theory 26 (2006) 2339, doi: 10.7151/dmgt.1298. 
[7]  J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, London, 1976.) 
[8]  J.A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111135, doi: 10.1016/0012365X(76)900789. 
[9]  E. Flandrin, H.A. Jung and H. Li, Hamiltonism, degrees sums and neighborhood intersections, Discrete Math. 90 (1991) 4152, doi: 10.1016/0012365X(91)90094I. 
[10]  Z. Wu, X. Zhang and X. Zhou, Hamiltonicity, neighborhood intersections and the partially square graphs, Discrete Math. 242 (2002) 245254, doi: 10.1016/S0012365X(00)003940. 
Received 23 September 2005
Revised 12 March 2007
Accepted 12 March 2007