ON IMPLICIT HEAVY SUBGRAPHS AND HAMILTONICITY OF 2-CONNECTED GRAPHS

被引：0

作者：

Zheng, Wei ^{[1
]}

Widel, Wojciech ^{[2
]}

Wang, Ligong ^{[1
]}

机构：

[1] Northwestern Polytech Univ, Dept Appl Math, Sch Sci, Xian 710072, Shaanxi, Peoples R China

[2] Univ Rennes, IRISA, CNRS, INSA Rennes, Rennes, France

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2021年 / 41卷 / 01期

基金：

中国国家自然科学基金;

关键词：

implicit degree; implicit o-heavy; implicit f-heavy; implicit c-heavy; Hamilton cycle; FORBIDDEN PAIRS; CYCLES; TRIPLES;

D O I：

10.7151/dmgt.2170

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A graph G of order n is implicit claw-heavy if in every induced copy of K-1,K-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.

引用

页码：167 / 181

页数：15

共 32 条

[1] [Anonymous], 1991, THESIS
[2] A GENERALIZATION OF FAN CONDITION FOR HAMILTONICITY, PANCYCLICITY, AND HAMILTONIAN CONNECTEDNESS
BEDROSSIAN, P
CHEN, G
SCHELP, RH
[J]. DISCRETE MATHEMATICS, 1993, 115 (1-3) : 39 - 50
[3] Bondy J.A, 2008, GRAPH THEORY
[4] Broersma Hajo., 1990, CONT METHODS GRAPH T, P181
[5] Dirac's minimum degree condition restricted to claws
Broersma, HJ
Ryjacek, Z
Schiermeyer, I
[J]. DISCRETE MATHEMATICS, 1997, 167 : 155 - 166
[6] Forbidden triples for hamiltonicity
Brousek, J
[J]. DISCRETE MATHEMATICS, 2002, 251 (1-3) : 71 - 76
[7] Degree conditions on induced claws
Cada, Roman
[J]. DISCRETE MATHEMATICS, 2008, 308 (23) : 5622 - 5631
[8] Fan-type implicit-heavy subgraphs for hamiltonicity of implicit claw-heavy graphs
Cai, Junqing
Zhang, Yuzhong
[J]. INFORMATION PROCESSING LETTERS, 2016, 116 (11) : 668 - 673
[9] Hamilton Cycles in Implicit 2-Heavy Graphs
Cai, Junqing
Li, Hao
[J]. GRAPHS AND COMBINATORICS, 2016, 32 (04) : 1329 - 1337
[10] An implicit degree condition for long cycles in 2-connected graphs
Chen, Bing
Zhang, Shenggui
[J]. APPLIED MATHEMATICS LETTERS, 2006, 19 (11) : 1148 - 1151

← 1 2 3 4 →