Geodesic
Heavy Subgraphs, Stability and Hamiltonicity
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 691-710.

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

Let G be a graph. Adopting the terminology of Broersma et al. and Čada, respectively, we say that G is 2-heavy if every induced claw (K1,3) of G contains two end-vertices each one has degree at least |V (G)|/2; and G is o-heavy if every induced claw of G contains two end-vertices with degree sum at least |V (G)| in G. In this paper, we introduce a new concept, and say that G is S-c-heavy if for a given graph S and every induced subgraph G′ of G isomorphic to S and every maximal clique C of G′, every non-trivial component of G′ − C contains a vertex of degree at least |V (G)|/2 in G. Our original motivation is a theorem of Hu from 1999 that can be stated, in terms of this concept, as every 2-connected 2-heavy and N-c-heavy graph is hamiltonian, where N is the graph obtained from a triangle by adding three disjoint pendant edges. In this paper, we will characterize all connected graphs S such that every 2-connected o-heavy and S-c-heavy graph is hamiltonian. Our work results in a different proof of a stronger version of Hu’s theorem. Furthermore, our main result improves or extends several previous results.
Keywords: heavy subgraphs, hamiltonian graphs, closure theory 
@article{DMGT_2017_37_3_a13,
     author = {Li, Binlong and Ning, Bo},
     title = {Heavy {Subgraphs,} {Stability} and {Hamiltonicity}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {691--710},
     publisher = {mathdoc},
     volume = {37},
     number = {3},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a13/}
}
TY  - JOUR
AU  - Li, Binlong
AU  - Ning, Bo
TI  - Heavy Subgraphs, Stability and Hamiltonicity
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 691
EP  - 710
VL  - 37
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a13/
LA  - en
ID  - DMGT_2017_37_3_a13
ER  - 
%0 Journal Article
%A Li, Binlong
%A Ning, Bo
%T Heavy Subgraphs, Stability and Hamiltonicity
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 691-710
%V 37
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a13/
%G en
%F DMGT_2017_37_3_a13
Li, Binlong; Ning, Bo. Heavy Subgraphs, Stability and Hamiltonicity. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 691-710. http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a13/

[1] P. Bedrossian, Forbidden Subgraph and Minimum Degree Conditons for Hamiltonicity (Ph.D. Thesis, Memphis State University, 1991).

[2] P. Bedrossian, G. Chen and R.H. Schelp, A generalization of Fan’s condition for Hamiltonicity, pancyclicity, and Hamiltonian connectedness, Discrete Math. 115 (1993) 39–50. doi:10.1016/0012-365X(93)90476-A

[3] L.W. Beineke, Characterizations of derived graphs, J. Combin. Theory Ser. B 9 (1970) 129–135. doi:10.1016/S0021-9800(70)80019-9

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

[5] H.J. Broersma, Z. Ryjáček and I. Schiermeyer, Dirac’s minimum degree condition restricted to claws, Discrete Math. 167/168 (1997) 155–166. doi:10.1016/S0012-365X(96)00224-5

[6] H.J. Broersma and H.J. Veldman, Restrictions on induced subgraphs ensuring hamiltonicity or pancyclicity of K 1,3 -free graphs, in: Contemporary Methods in Graph Theory (BI Wissenschaftsverlag, Mannheim 1990) 181–194.

[7] J. Brousek, Minimal 2 -connected non-Hamiltonian claw-free graphs, Discrete Math. 191 (1998) 57–64. doi:10.1016/S0012-365X(98)00093-4

[8] J. Brousek, Z. Ryjáček and O. Favaron, Forbidden subgraphs, hamiltonicity and closure in claw-free graphs, Discrete Math. 196 (1999) 29–50. doi:10.1016/S0012-365X(98)00334-3

[9] G. Chen, B. Wei and X. Zhang, Degree-light-free graphs and hamiltonian cycles, Graphs Combin. 17 (2001) 409–434. doi:10.1007/s003730170018

[10] R. Čada, Degree conditions on induced claws, Discrete Math. 308 (2008) 5622–5631. doi:10.1016/j.disc.2007.10.026

[11] G.A. Dirac, Some theorems on abstract graphs, Proc. London. Math. Soc. 2 (1952) 69–81. doi:10.1112/plms/s3-2.1.69

[12] D. Duffus, M. Jacboson and R.J. Gould, Forbidden subgraphs and the Hamiltonian theme, in: The Theory and Applications of Graphs (Wiley, New York, 1981) 297–316.

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

[14] R.J. Faudree and R.J. Gould, Characterizing forbidden pairs for hamiltonian properties, Discrete Math. 173 (1997) 45–60. doi:10.1016/S0012-365X(96)00147-1

[15] R.J. Faudree, R.J. Gould, Z. Ryjáček and I. Schiermeyer, Forbidden subgraphs and pancyclicity, Congr. Numer. 109 (1995) 13–32.

[16] R.J. Gould and M.S. Jacobson, Forbidden subgraphs and hamiltonian properties of graphs, Discrete Math. 42 (1982) 189–196. doi:10.1016/0012-365X(82)90216-3

[17] Z. Hu, A generalization of Fan’s condition and forbidden subgraph conditions for hamiltonicity, Discrete Math. 196 (1999) 167–175. doi:10.1016/S0012-365X(98)00200-3

[18] B. Li, Z. Ryjáček, Y. Wang and S. Zhang, Pairs of heavy subgraphs for Hamiltonicity of 2 -connected graphs, SIAM J. Discrete Math. 26 (2012) 1088–1103. doi:10.1137/11084786X

[19] G. Li, B. Wei and T. Gao, A structural method for Hamiltonian graphs, Australas. J. Combin. 11 (1995) 257–262.

[20] B. Ning and S. Zhang, Ore- and Fan-type heavy subgraphs for hamiltonicity of 2 -connected graphs, Discrete Math. 313 (2013) 1715–1725. doi:10.1016/j.disc.2013.04.023

[21] B. Ning, S. Zhang and B. Li, Solution to a problem on hamiltonicity of graphs under Ore- and Fan-type heavy subgraph conditions, Graphs Combin. 32 (2016) 1125–1135. doi:10.1007/s00373-015-1619-1

[22] O. Ore, Note on Hamilton circuit, Amer. Math. Monthly 67 (1960) 55.

[23] 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