Geodesic
2-Connected Hamiltonian Claw-Free Graphs Involving Degree Sum of Adjacent Vertices
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 85-106.

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

For a graph H, define σ_2(H)=min{d(u)+d(v)|uv∈E(H)}. Let H be a 2-connected claw-free simple graph of order n with δ(H) ≥ 3. In [J. Graph Theory 86 (2017) 193–212], Chen proved that if σ_2(H)≥n/2−1 and n is sufficiently large, then H is Hamiltonian with two families of exceptions. In this paper, we refine the result. We focus on the condition σ_2(H)≥2n/5−1, and characterize non-Hamiltonian 2-connected claw-free graphs H of order n sufficiently large with σ_2(H)≥2n/5−1. As byproducts, we prove that there are exactly six graphs in the family of 2-edge-connected triangle-free graphs of order at most seven that have no spanning closed trail and give an improvement of a result of Veldman in [Discrete Math. 124 (1994) 229–239].
Keywords: Hamiltonian cycle, degree sum, dominating closed trail, closure 
@article{DMGT_2020_40_1_a6,
     author = {Tian, Tao and Xiong, Liming},
     title = {2-Connected {Hamiltonian} {Claw-Free} {Graphs} {Involving} {Degree} {Sum} of {Adjacent} {Vertices}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {85--106},
     publisher = {mathdoc},
     volume = {40},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a6/}
}
TY  - JOUR
AU  - Tian, Tao
AU  - Xiong, Liming
TI  - 2-Connected Hamiltonian Claw-Free Graphs Involving Degree Sum of Adjacent Vertices
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 85
EP  - 106
VL  - 40
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a6/
LA  - en
ID  - DMGT_2020_40_1_a6
ER  - 
%0 Journal Article
%A Tian, Tao
%A Xiong, Liming
%T 2-Connected Hamiltonian Claw-Free Graphs Involving Degree Sum of Adjacent Vertices
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 85-106
%V 40
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a6/
%G en
%F DMGT_2020_40_1_a6
Tian, Tao; Xiong, Liming. 2-Connected Hamiltonian Claw-Free Graphs Involving Degree Sum of Adjacent Vertices. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 85-106. http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a6/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).

[2] P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–45. doi:10.1016/S0012-365X(95)00149-Q

[3] P.A. Catlin, Z. Han and H.-J Lai, Graphs without spanning Eulerian trails, Discrete Math. 160 (1996) 81–91. doi:10.1002/jgt.22120

[4] Z.-H. Chen, Hamiltonicity and degrees of adjacent vertices in claw-free graphs, J. Graph Theory 86 (2017) 193–212. doi:10.1002/jgt.22120

[5] G.H. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory Ser. B 37 (1981) 221–227. doi:10.1016/0095-8956(84)90054-6

[6] R. Faudree, E. Flandrin and Z. Ryjáček, Claw-free graphs — A survey, Discrete Math. 164 (1997) 87–147. doi:10.1016/S0012-365X(96)00045-3

[7] O. Favaron, E. Flandrin, H. Li and Z. Ryjáček, Clique covering and degree conditions for Hamiltonicity in claw-free graphs, Discrete Math. 236 (2001) 65–80. doi:10.1016/S0012-365X(00)00432-5

[8] R. Gould, Recent advances on the Hamiltonian problem: Survey III, Graphs Combin. 30 (2014) 1–46. doi:10.1007/s00373-013-1377-x

[9] F. Harary and C.St.J.A. Nash-Williams, On Eulerian and Hamiltonian graphs and line graphs, Canad. Math. Bull. 8 (1965) 701–710. doi:10.4153/CMB-1965-051-3

[10] O. Kovářík, M. Mulač and Z. Ryjáček, A note on degree conditions for Hamiltonicity in 2 -connected claw-free graphs, Discrete Math. 244 (2002) 253–268. doi:10.1016/S0012-365X(01)00088-7

[11] H. Li, M. Lu, F. Tian and B. Wei, Hamiltonian cycles in 2 -connected claw-free graphs with at most 5 δ − 5 vertices, Congr. Numer. 122 (1996) 184–202.

[12] M.M. Matthews and D.P. Sumner, Longest path and cycle in K 1,3 -free graphs, J. Graph Theory 9 (1985) 269–277. doi:10.1002/jgt.3190090208

[13] O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55. doi:10.2307/2308928

[14] Z. Ryjáček, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B 70 (1997) 217–224. doi:10.1006/jctb.1996.1732

[15] Y. Shao, Claw-free graphs and line graphs, Ph.D dissertation (West Virginia University, 2005).

[16] H.J. Veldman, On dominating and spanning circuits in graphs, Discrete Math. 124 (1994) 229–239. doi:10.1016/0012-365X(92)00063-W

[17] C.Q. Zhang, Hamilton cycles in claw-free graphs, J. Graph Theory 12 (1988) 209–216. doi:10.1002/jgt.3190120211