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

Abstract

top
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.

How to cite

top

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 -

References

top
  1. [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. [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. [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. [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. [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. [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. [7] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, London, 1976.) Zbl1226.05083
  8. [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. [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. [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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.