Extension of several sufficient conditions for Hamiltonian graphs

Ahmed Ainouche

Discussiones Mathematicae Graph Theory (2006)

  • Volume: 26, Issue: 1, page 23-39
  • ISSN: 2083-5892

Abstract

top
Let G be a 2-connected graph of order n. Suppose that for all 3-independent sets X in G, there exists a vertex u in X such that |N(X∖u)|+d(u) ≥ n-1. Using the concept of dual closure, we prove that 1. G is hamiltonian if and only if its 0-dual closure is either complete or the cycle C₇ 2. G is nonhamiltonian if and only if its 0-dual closure is either the graph ( K r ∪ K ₛ ∪ K ₜ ) ∨ K ₂ , 1 ≤ r ≤ s ≤ t or the graph ( ( n + 1 ) / 2 ) K ₁ ∨ K ( n - 1 ) / 2 . It follows that it takes a polynomial time to check the hamiltonicity or the nonhamiltonicity of a graph satisfying the above condition. From this main result we derive a large number of extensions of previous sufficient conditions for hamiltonian graphs. All these results are sharp.

How to cite

top

Ahmed Ainouche. "Extension of several sufficient conditions for Hamiltonian graphs." Discussiones Mathematicae Graph Theory 26.1 (2006): 23-39. <http://eudml.org/doc/270300>.

@article{AhmedAinouche2006,
abstract = {Let G be a 2-connected graph of order n. Suppose that for all 3-independent sets X in G, there exists a vertex u in X such that |N(X∖u)|+d(u) ≥ n-1. Using the concept of dual closure, we prove that 1. G is hamiltonian if and only if its 0-dual closure is either complete or the cycle C₇ 2. G is nonhamiltonian if and only if its 0-dual closure is either the graph $(K_r ∪ Kₛ ∪ Kₜ) ∨ K₂$, 1 ≤ r ≤ s ≤ t or the graph $((n+1)/2)K₁ ∨ K_\{(n-1)/2\}$. It follows that it takes a polynomial time to check the hamiltonicity or the nonhamiltonicity of a graph satisfying the above condition. From this main result we derive a large number of extensions of previous sufficient conditions for hamiltonian graphs. All these results are sharp.},
author = {Ahmed Ainouche},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hamiltonian graph; dual closure; neighborhood closure},
language = {eng},
number = {1},
pages = {23-39},
title = {Extension of several sufficient conditions for Hamiltonian graphs},
url = {http://eudml.org/doc/270300},
volume = {26},
year = {2006},
}

TY - JOUR
AU - Ahmed Ainouche
TI - Extension of several sufficient conditions for Hamiltonian graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2006
VL - 26
IS - 1
SP - 23
EP - 39
AB - Let G be a 2-connected graph of order n. Suppose that for all 3-independent sets X in G, there exists a vertex u in X such that |N(X∖u)|+d(u) ≥ n-1. Using the concept of dual closure, we prove that 1. G is hamiltonian if and only if its 0-dual closure is either complete or the cycle C₇ 2. G is nonhamiltonian if and only if its 0-dual closure is either the graph $(K_r ∪ Kₛ ∪ Kₜ) ∨ K₂$, 1 ≤ r ≤ s ≤ t or the graph $((n+1)/2)K₁ ∨ K_{(n-1)/2}$. It follows that it takes a polynomial time to check the hamiltonicity or the nonhamiltonicity of a graph satisfying the above condition. From this main result we derive a large number of extensions of previous sufficient conditions for hamiltonian graphs. All these results are sharp.
LA - eng
KW - hamiltonian graph; dual closure; neighborhood closure
UR - http://eudml.org/doc/270300
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, A common generalization of Chvàtal-Erdös and Fraisse's sufficient conditions for hamiltonian graphs, Discrete Math. 142 (1995) 1-19, doi: 10.1016/0012-365X(94)00002-Z. Zbl0834.05033
  3. [3] A. Ainouche, Extensions of a closure condition: the β-closure (Rapport de Recherche CEREGMIA, 2001). 
  4. [4] A. Ainouche and I. Schiermeyer, 0-dual closure for several classes of graphs, Graphs and Combinatorics 19 (2003) 297-307, doi: 10.1007/s00373-002-0523-y. 
  5. [5] A. Ainouche and S. Lapiquonne, Variations on a strong sufficient condition for hamiltonian graphs, submitted. 
  6. [6] J.A. Bondy, Longest paths and cycles in graphs of high degree, Research Report CORR 80-16, Dept. of Combinatorics and Optimization, University of Waterloo, Ont. Canada. 
  7. [7] 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
  8. [8] G. Chen, One sufficient condition for Hamiltonian Graphs, J. Graph Theory 14 (1990) 501-508, doi: 10.1002/jgt.3190140414. Zbl0721.05043
  9. [9] G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952) 69-81, doi: 10.1112/plms/s3-2.1.69. Zbl0047.17001
  10. [10] R.J. Faudree, R.J. Gould, M.S. Jacobson and L.S. Lesniak, Neighborhood unions and highly Hamiltonian Graphs, Ars Combin. 31 (1991) 139-148. Zbl0739.05056
  11. [11] R.J. Faudree, R.J. Gould, M.S. Jacobson and R.H. Shelp, Neighborhood unions and Hamiltonian properties in Graphs, J. Combin. Theory (B) 47 (1989) 1-9, doi: 10.1016/0095-8956(89)90060-9. 
  12. [12] 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
  13. [13] P. Fraisse, A new sufficient condition for Hamiltonian Graphs, J. Graph Theory 10 (1986) 405-409, doi: 10.1002/jgt.3190100316. Zbl0606.05043
  14. [14] T. Feng, A note on the paper A new sufficient condition for hamiltonian graph, Systems Sci. Math. Sci. 5 (1992) 81-83. Zbl0774.05061
  15. [15] I. Schiermeyer, Computation of the 0-dual closure for hamiltonian graphs, Discrete Math. 111 (1993) 455-464, doi: 10.1016/0012-365X(93)90183-T. Zbl0789.05060
  16. [16] O. Ore, Note on Hamiltonian circuits, Am. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928. 

NotesEmbed ?

top

You must be logged in to post comments.