Connected [a, b]-factors in K1,n-free graphs containing an [a, b]-factor

被引:4
|
作者
Tokuda, T [1 ]
机构
[1] Keio Univ, Fac Sci & Technol, Dept Math, Kohoku Ku, Yokohama, Kanagawa 223, Japan
关键词
graph; factor; connected factor; K-1; K-n-free;
D O I
10.1016/S0012-365X(99)00113-2
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A graph G is called K-1,K-n-free if G has no induced subgraph isomorphic to K-1,K-n. Let n, a, and b be integers with n greater than or equal to 3, a greater than or equal to 1, and b greater than or equal to a(n - 2) + 2. We prove that every connected K-1,K-n-free graph G has a connected [a,b]-factor if G contains an [a,b]-factor. This result is sharp in the sense that there exists a connected K-l,K-n-free graph which has an [a,b]-factor but no connected [a,b]-factor for b less than or equal to a(n - 2) + 1. (C) 1999 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:293 / 298
页数:6
相关论文
共 50 条
  • [1] Connected factors in K1,n-free graphs containing an [a, b]-factor
    Tokuda, Taro
    DISCRETE MATHEMATICS, 2006, 306 (21) : 2806 - 2810
  • [2] Connected Factors in K1,n-free Graphs Containing a (g, f)-factor
    Baoguang Xu
    Zhenhong Liu
    Taro Tokuda
    Graphs and Combinatorics, 1998, 14 (4) : 393 - 395
  • [3] Connected factors in K1,n-free graphs containing a (g,f)-factor
    Xu, BG
    Liu, ZH
    Tokuda, T
    GRAPHS AND COMBINATORICS, 1998, 14 (04) : 393 - 395
  • [4] REGULAR FACTORS IN K1,N-FREE GRAPHS
    EGAWA, Y
    OTA, K
    JOURNAL OF GRAPH THEORY, 1991, 15 (03) : 337 - 344
  • [5] K1,n-free图的[a,b]-因子
    徐睿
    山东大学学报(自然科学版), 1996, (02) : 173 - 177
  • [6] Stability Number and f-factor in K1,n-free Graphs
    Cai, Jiansheng
    Liu, Guizhen
    ARS COMBINATORIA, 2008, 89 : 235 - 242
  • [7] Connected even factors in {K1,l, K1,l + e}-free graphs
    Duan, Fang
    Zhang, Weijuan
    Wang, Guoping
    ARS COMBINATORIA, 2014, 115 : 385 - 389
  • [8] Existence of 3-factors in K1,n-free graphs with connectivity and edge-connectivity conditions
    Kotani, Keiko
    Nishida, Shuto
    AUSTRALASIAN JOURNAL OF COMBINATORICS, 2021, 79 : 106 - 122
  • [9] The L(2,1)-labeling of K1,n-free graphs and its applications
    Shao, Zhendong
    Yeh, Roger K.
    Poon, Kin Keung
    Shiu, Wai Chee
    APPLIED MATHEMATICS LETTERS, 2008, 21 (11) : 1188 - 1193
  • [10] ON CONNECTED FACTORS IN K1,3-FREE GRAPHS
    李国君
    刘振宏
    Acta Mathematicae Applicatae Sinica(English Series), 1998, (01) : 43 - 47