Extension of several sufficient conditions for Hamiltonian graphs
Discussiones Mathematicae Graph Theory (2006)
- Volume: 26, Issue: 1, page 23-39
- ISSN: 2083-5892
Access Full Article
topAbstract
topHow to cite
topAhmed 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] 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, 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] A. Ainouche, Extensions of a closure condition: the β-closure (Rapport de Recherche CEREGMIA, 2001).
- [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] A. Ainouche and S. Lapiquonne, Variations on a strong sufficient condition for hamiltonian graphs, submitted.
- [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] 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] G. Chen, One sufficient condition for Hamiltonian Graphs, J. Graph Theory 14 (1990) 501-508, doi: 10.1002/jgt.3190140414. Zbl0721.05043
- [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] 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] 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] 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] P. Fraisse, A new sufficient condition for Hamiltonian Graphs, J. Graph Theory 10 (1986) 405-409, doi: 10.1002/jgt.3190100316. Zbl0606.05043
- [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] 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] O. Ore, Note on Hamiltonian circuits, Am. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928.
Citations in EuDML Documents
topNotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.