Discussiones Mathematicae Graph Theory 27(2) (2007) 229-240
doi: 10.7151/dmgt.1357

[BIBTex] [PDF] [PS]

VARIATIONS ON A SUFFICIENT CONDITION FOR HAMILTONIAN GRAPHS

Ahmed Ainouche  and  Serge Lapiquonne

UAG - CEREGMIA - GRIMAAG
B.P. 7209, 97275 Schoelcher Cedex, Martinique FRANCE
e-mail: a.ainouche@martinique.univ-ag.fr
e-mail: s.lapiquonne@martinique.univ-ag.fr Abstract 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 NG(x) ⊆ NG[u]∪NG[v], where NG[x] = NG(x)∪{x}. In particular, this condition is satisfied if x does not center a claw (an induced K1,3). Clearly G ⊆ G* ⊆ G2, where G2 is the square of G. For any independent triple X = {x,y,z} we define


σ
 

3 
(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 [`(σ)]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 2-connected 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.

References

[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.
[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.
[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.
[4] A. Ainouche and M. Kouider, Hamiltonism and Partially Square Graphs, Graphs and Combinatorics 15 (1999) 257-265, doi: 10.1007/s003730050059.
[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.
[6] A. Ainouche, Extension of several sufficient conditions for hamiltonian graphs, Discuss. Math. Graph Theory 26 (2006) 23-39, 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) 111-135, doi: 10.1016/0012-365X(76)90078-9.
[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.
[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.

Received 23 September 2005
Revised 12 March 2007
Accepted 12 March 2007