Geodesic
Remarks on partially square graphs, hamiltonicity and circumference
Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 2, pp. 255-266

Voir la notice de l'article provenant de la source Library of Science

Given a graph G, its partially square graph G* is a graph obtained by adding an edge (u,v) for each pair u, v of vertices of G at distance 2 whenever the vertices u and 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 the case where G is a claw-free graph, G* is equal to G². We define σ°ₜ = min ∑_x∈S d_G(x):S is an independent set in G* and |S| = t. We give for hamiltonicity and circumference new sufficient conditions depending on σ° and we improve some known results.
Keywords: partially square graph, claw-free graph, independent set, hamiltonicity and circumference 
Kheddouci, Hamamache. Remarks on partially square graphs, hamiltonicity and circumference. Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 2, pp. 255-266. http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a9/
@article{DMGT_2001_21_2_a9,
     author = {Kheddouci, Hamamache},
     title = {Remarks on partially square graphs, hamiltonicity and circumference},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {255--266},
     year = {2001},
     volume = {21},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a9/}
}
TY  - JOUR
AU  - Kheddouci, Hamamache
TI  - Remarks on partially square graphs, hamiltonicity and circumference
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2001
SP  - 255
EP  - 266
VL  - 21
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a9/
LA  - en
ID  - DMGT_2001_21_2_a9
ER  - 
%0 Journal Article
%A Kheddouci, Hamamache
%T Remarks on partially square graphs, hamiltonicity and circumference
%J Discussiones Mathematicae. Graph Theory
%D 2001
%P 255-266
%V 21
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a9/
%G en
%F DMGT_2001_21_2_a9

[1] A. Ainouche, An improvement of Fraisse's sufficient condition for hamiltonian graphs, J. Graph Theory 16 (1992) 529-543, doi: 10.1002/jgt.3190160602.

[2] A. Ainouche and M. Kouider, Hamiltonism and partially square graph, Graphs and Combinatorics 15 (1999) 257-265, doi: 10.1007/s003730050059.

[3] J.C. Bermond, On Hamiltonian Walks, in: C.St.J.A. Nash-Wiliams and J. Sheehan, eds, Proceedings of the Fifth British Combinatorial Conference, Aberdeen, 1975 (Congr. Numerantium XV, Utilitas Math. Publ. Inc., 1975) 41-51.

[4] A. Bondy, Longest paths and cycles in graphs of high degree, Research report CORR 80-16 Dept of Combinatorics and Optimization (University of Waterloo, 1980).

[5] I. Fournier and P. Fraisse, On a conjecture of Bondy, J. Combin. Theory (B) 39 (1985) 17-26, doi: 10.1016/0095-8956(85)90035-8.