# Variations on a sufficient condition for Hamiltonian graphs

Ahmed Ainouche; Serge Lapiquonne

Discussiones Mathematicae Graph Theory (2007)

- Volume: 27, Issue: 2, page 229-240
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topAhmed Ainouche, and Serge Lapiquonne. "Variations on a sufficient condition for Hamiltonian graphs." Discussiones Mathematicae Graph Theory 27.2 (2007): 229-240. <http://eudml.org/doc/270470>.

@article{AhmedAinouche2007,

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 $N_G(x) ⊆ N_G[u] ∪ N_G[v]$, where $N_G[x] = N_G(x) ∪ \{x\}$. In particular, this condition is satisfied if x does not center a claw (an induced $K_\{1,3\}$). 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.},

author = {Ahmed Ainouche, Serge Lapiquonne},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {cycles; partially square graph; degree sum; independent sets; neighborhood unions and intersections; dual closure},

language = {eng},

number = {2},

pages = {229-240},

title = {Variations on a sufficient condition for Hamiltonian graphs},

url = {http://eudml.org/doc/270470},

volume = {27},

year = {2007},

}

TY - JOUR

AU - Ahmed Ainouche

AU - Serge Lapiquonne

TI - Variations on a sufficient condition for Hamiltonian graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2007

VL - 27

IS - 2

SP - 229

EP - 240

AB - 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 $N_G(x) ⊆ N_G[u] ∪ N_G[v]$, where $N_G[x] = N_G(x) ∪ {x}$. In particular, this condition is satisfied if x does not center a claw (an induced $K_{1,3}$). 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.

LA - eng

KW - cycles; partially square graph; degree sum; independent sets; neighborhood unions and intersections; dual closure

UR - http://eudml.org/doc/270470

ER -

## References

top- [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. Zbl0770.05070
- [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. Zbl0958.05084
- [4] A. Ainouche and M. Kouider, Hamiltonism and Partially Square Graphs, Graphs and Combinatorics 15 (1999) 257-265, doi: 10.1007/s003730050059. Zbl0933.05096
- [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.) Zbl1226.05083
- [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. Zbl0331.05138
- [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. Zbl0746.05038
- [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. Zbl0995.05085