Dirac's minimum degree condition restricted to claws

被引:21
作者
Broersma, HJ
Ryjacek, Z
Schiermeyer, I
机构
[1] UNIV TWENTE,FAC APPL MATH,NL-7500 AE ENSCHEDE,NETHERLANDS
[2] UNIV W BOHEMIA,DEPT MATH,PLZEN 30614,CZECH REPUBLIC
[3] TU COTTBUS,LEHRSTUHL DISKRETE MATH & GRUNDLAGEN INFORMAT,D-03013 COTTBUS,GERMANY
关键词
Hamilton cycle; Hamiltonian graph; minimum degree condition; induced subgraph; claw; claw-free graph; local connectivity; 1-tough graph; perfect matching;
D O I
10.1016/S0012-365X(96)00224-5
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G be a graph on n greater than or equal to 3 vertices. Dirac's minimum degree condition is the condition that all vertices of G have degree at least 1/2n. This is a well-known sufficient condition for the existence of a Hamilton cycle in G. We give related sufficiency conditions for the existence of a Hamilton cycle or a perfect matching involving a restriction of Dirac's minimum degree condition to certain subsets of the vertices. For this purpose we define G to be 1-heavy (2-heavy) if at least one (two) of the end vertices of each induced subgraph of G isomorphic to K-1,K-3 (a claw) has (have) degree at least 1/2n. Thus, every claw-free graph is 2-heavy, and every 2-heavy graph is 1-heavy. We show that a 1-heavy or a 2-heavy graph G has a Hamilton cycle or a perfect matching if we impose certain additional conditions on G involving numbers of common neighbours, (local) connectivity, and forbidden induced subgraphs. These results generalize or extend previous work of Broersma & Veldman, Dirac, Fan, Faudree et al., Goodman & Hedetniemi, Las Vergnas, Oberly & Sumner, Ore, Shi, and Sumner.
引用
收藏
页码:155 / 166
页数:12
相关论文
共 18 条
  • [1] [Anonymous], 1990, CONT METHODS GRAPH T
  • [2] [Anonymous], 1980, LONGEST PATHS CYCLES
  • [3] 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
  • [4] CYCLES THROUGH SPECIFIED VERTICES
    BOLLOBAS, B
    BRIGHTWELL, G
    [J]. COMBINATORICA, 1993, 13 (02) : 147 - 155
  • [5] METHOD IN GRAPH THEORY
    BONDY, JA
    CHVATAL, V
    [J]. DISCRETE MATHEMATICS, 1976, 15 (02) : 111 - 135
  • [6] BONDY JA, 1976, GRAPH THEORY APPLICA
  • [7] Chvatal V., 1972, DISCRETE MATH, V2, P111, DOI DOI 10.1016/0012-365X(72)90079-9
  • [8] Dirac G. A., 1952, Proc. Lond. Math. Soc, V3-2, P69, DOI [10.1112/plms/s3-2.1.69, DOI 10.1112/PLMS/S3-2.1.69]
  • [9] NEW SUFFICIENT CONDITIONS FOR CYCLES IN GRAPHS
    FAN, GH
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1984, 37 (03) : 221 - 227
  • [10] FAUDREE RJ, 1994, FORBIDDEN SUBGRAPHS