Variations on a sufficient condition for Hamiltonian graphs

Ahmed 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 -