Geodesic
Variations on a sufficient condition for Hamiltonian graphs
Discussiones Mathematicae. Graph Theory, Tome 27 (2007) no. 2, pp. 229-240 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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
Keywords: cycles, partially square graph, degree sum, independent sets, neighborhood unions and intersections, dual closure 
@article{DMGT_2007_27_2_a1,
     author = {Ainouche, Ahmed and Lapiquonne, Serge},
     title = {Variations on a sufficient condition for {Hamiltonian} graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {229--240},
     year = {2007},
     volume = {27},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2007_27_2_a1/}
}
TY  - JOUR
AU  - Ainouche, Ahmed
AU  - Lapiquonne, Serge
TI  - Variations on a sufficient condition for Hamiltonian graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2007
SP  - 229
EP  - 240
VL  - 27
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2007_27_2_a1/
LA  - en
ID  - DMGT_2007_27_2_a1
ER  - 
%0 Journal Article
%A Ainouche, Ahmed
%A Lapiquonne, Serge
%T Variations on a sufficient condition for Hamiltonian graphs
%J Discussiones Mathematicae. Graph Theory
%D 2007
%P 229-240
%V 27
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2007_27_2_a1/
%G en
%F DMGT_2007_27_2_a1
Ainouche, Ahmed; Lapiquonne, Serge. Variations on a sufficient condition for Hamiltonian graphs. Discussiones Mathematicae. Graph Theory, Tome 27 (2007) no. 2, pp. 229-240. http://geodesic.mathdoc.fr/item/DMGT_2007_27_2_a1/

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

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

[4] A. Ainouche and M. Kouider, Hamiltonism and Partially Square Graphs, Graphs and Combinatorics 15 (1999) 257-265, doi: 10.1007/s003730050059.

[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.)

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

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

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