Geodesic
On Implicit Heavy Subgraphs and Hamiltonicity of 2-Connected Graphs
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 167-181.

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

A graph G of order n is implicit claw-heavy if in every induced copy of K1,3 in G there are two non-adjacent vertices with sum of their implicit degrees at least n. We study various implicit degree conditions (including, but not limiting to, Ore- and Fan-type conditions) imposing of which on specific induced subgraphs of a 2-connected implicit claw-heavy graph ensures its Hamiltonicity. In particular, we improve a recent result of [X. Huang, Implicit degree condition for Hamiltonicity of 2-heavy graphs, Discrete Appl. Math. 219 (2017) 126–131] and complete the characterizations of pairs of o-heavy and f-heavy subgraphs for Hamiltonicity of 2-connected graphs.
Keywords: implicit degree, implicit o-heavy, implicit f-heavy, implicit c-heavy, Hamilton cycle 
@article{DMGT_2021_41_1_a10,
     author = {Zheng, Wei and Wide{\l}, Wojciech and Wang, Ligong},
     title = {On {Implicit} {Heavy} {Subgraphs} and {Hamiltonicity} of {2-Connected} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {167--181},
     publisher = {mathdoc},
     volume = {41},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a10/}
}
TY  - JOUR
AU  - Zheng, Wei
AU  - Wideł, Wojciech
AU  - Wang, Ligong
TI  - On Implicit Heavy Subgraphs and Hamiltonicity of 2-Connected Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 167
EP  - 181
VL  - 41
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a10/
LA  - en
ID  - DMGT_2021_41_1_a10
ER  - 
%0 Journal Article
%A Zheng, Wei
%A Wideł, Wojciech
%A Wang, Ligong
%T On Implicit Heavy Subgraphs and Hamiltonicity of 2-Connected Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 167-181
%V 41
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a10/
%G en
%F DMGT_2021_41_1_a10
Zheng, Wei; Wideł, Wojciech; Wang, Ligong. On Implicit Heavy Subgraphs and Hamiltonicity of 2-Connected Graphs. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 167-181. http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a10/

[1] P. Bedrossian, Forbidden Subgraph and Minimum Degree Conditions for Hamiltonicity, Ph.D. Thesis (Memphis State University, USA, 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] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, GTM 244 (Springer, Berlin, 2008).

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

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

[6] J. Brousek, Forbidden triples for Hamiltonicity, Discrete Math. 251 (2002) 71–76. doi: 10.1016/S0012-365X(01)00326-0

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

[8] J. Cai and H. Li, Hamilton cycles in implicit 2- heavy graphs, Graphs Combin. 32 (2016) 1329–1337. doi: 10.1007/s00373-015-1669-4

[9] J. Cai and Y. Zhang, Fan-type implicit-heavy subgraphs for Hamiltonicity of implicit claw-heavy graphs, Inform. Process. Lett. 116 (2016) 668–673. doi: 10.1016/j.ipl.2016.06.012

[10] G. Chen, B. Wei and X. Zhang, Forbidden graphs and Hamiltonian cycles, preprint, 1995.

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

[12] B. Chen and S. Zhang, An implicit degree condition for long cycles in 2- connected graphs, Appl. Math. Lett. 19 (2006) 1148–1151. doi: 10.1016/j.aml.2005.12.006

[13] V. Chvátal and P. Erdős, A note on Hamiltonian circuits, Discrete Math. 2 (1972) 111–113. doi: 10.1016/0012-365X(72)90079-9

[14] D. Duffus, R.J. Gould and M.S. Jacobson, Forbidden subgraphs and the Hamiltonian theme, Proceedings of the 4th International Conference on the Theory and Applications of Graphs, Kalamazoo, 1980 (Wiley, New York, 1981) 297–316.

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

[16] R. Faudree, Z. Ryjáček and I. Schiermeyer, Forbidden subgraphs and cycle extendability, J. Combin. Math. Combin. Comput. 19 (1995) 109–128.

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

[18] S. Goodman and S.T. Hedetniemi, Sufficient conditions for a graph to be Hamiltonian, J. Combin. Theory Ser. B 16 (1974) 175–180. doi: 10.1016/0095-8956(74)90061-6

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

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

[21] X. Huang, Hamilton cycles in implicit claw-heavy graphs, Inform. Process. Lett. 114 (2014) 676–679. doi: 10.1016/j.ipl.2014.06.007

[22] X. Huang, Implicit degree condition for Hamiltonicity of 2-heavy graphs, Discrete Appl. Math. 219 (2017) 126–131. doi: 10.1016/j.dam.2016.10.031

[23] B. Li and B. Ning, Heavy subgraphs, stability and Hamiltonicity, Discuss. Math. Graph Theory 37 (2017) 691–710. doi: 10.7151/dmgt.1967

[24] B. Li, B. Ning and S. Zhang, Degree conditions restricted to induced paths for Hamiltonicity of claw-heavy graphs, Acta Math. Sin. (Engl. Ser.) 33 (2017) 301–310. doi: 10.1007/s10114-016-5735-5

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

[26] B. Li and P. Vrána, Forbidden pairs of disconnected graphs implying Hamiltonicity, J. Graph Theory 84 (2017) 249–261. doi: 10.1002/jgt.22024

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

[28] H. Li, W. Ning and J. Cai, An implicit degree condition for cyclability in graphs, Lecture Notes in Comput. Sci. 6681 (2011) 82–89. doi: 10.1007/978-3-642-21204-8_12

[29] B. Ning, Fan-type degree condition restricted to triples of induced subgraphs ensuring Hamiltonicity, Inform. Process. Lett. 113 (2013) 823–826. doi: 10.1016/j.ipl.2013.07.014

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

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

[32] Y. Zhu, H. Li and X. Deng, Implicit-degrees and circumferences, Graphs Combin. 5 (1989) 283–290. doi: 10.1007/BF01788680