Connected Factors in K1,n-free Graphs Containing a (g, f)-factor

被引:0
作者
Baoguang Xu
Zhenhong Liu
Taro Tokuda
机构
[1] Institute of Systems Science,
[2] Academia Sinica,undefined
[3] Beijing,undefined
[4] P.R.C. 100080,undefined
[5] Department of Mathematics,undefined
[6] Faculty of Science and Technology,undefined
[7] Keio University,undefined
[8] 3-14-1 Hiyoshi,undefined
[9] Kohoku-ku,undefined
[10] Yokohama 223-8522,undefined
[11] Japan,undefined
关键词
D O I
10.1007/PL00021186
中图分类号
学科分类号
摘要
Let G be a connected K1,n-free graph (n≥3), f and g be positive integer-valued functions defined on V(G) with g(v)≤f(v) for all v∈V(G). We prove that G contains a connected (g,f+n−1)-factor if G has a (g,f)-factor. This result is sharp from the point of view that there exists a connected K1,n-free graph which has a (g,f)-factor but no connected (g,f+n−2)-factor for all pairs of positive integer-valued functions g and f with g=f.
引用
收藏
页码:393 / 395
页数:2
相关论文
共 50 条
  • [21] REGULAR FACTORS IN K1,3-FREE GRAPHS
    CHOUDUM, SA
    PAULRAJ, MS
    JOURNAL OF GRAPH THEORY, 1991, 15 (03) : 259 - 265
  • [22] Binding Number and Connected ( g, f+1)-factors in graphs
    Cai, Jiansheng
    Liu, Guizhen
    Hou, Jianfeng
    COMPUTATIONAL SCIENCE - ICCS 2007, PT 3, PROCEEDINGS, 2007, 4489 : 313 - +
  • [23] HAMILTONICITY FOR K1,(R)-FREE GRAPHS
    CHEN, G
    SCHELP, RH
    JOURNAL OF GRAPH THEORY, 1995, 20 (04) : 423 - 439
  • [24] CONNECTED, LOCALLY 2-CONNECTED, K1,3-FREE GRAPHS ARE PANCONNECTED
    KANETKAR, SV
    RAO, PR
    JOURNAL OF GRAPH THEORY, 1984, 8 (03) : 347 - 353
  • [25] Connected [k, k + 1]-factors of graphs 1
    Institute of Systems Science, Academia Sinica, Beijing 100080, China
    Discrete Math, 1-3 (1-16):
  • [26] Hamiltonicity of 2-connected {K1,4, K1,4 + e]-free graphs
    Li, R
    DISCRETE MATHEMATICS, 2004, 287 (1-3) : 69 - 76
  • [27] A characterization of 2-connected {K1,3, N3,1,1}-free non-Hamiltonian graphs
    Chiba, Shuya
    Furuya, Michitaka
    DISCRETE MATHEMATICS, 2021, 344 (05)
  • [28] Spanning trees with at most k leaves in 2-connected K1,r-free graphs
    Chen, Guantao
    Chen, Yuan
    Hu, Zhiquan
    Zhang, Shunzhe
    APPLIED MATHEMATICS AND COMPUTATION, 2023, 445
  • [29] On Ramsey (K1,m, g)-minimal graphs
    Borowiecka-Olszewska, Marta
    Haluszczak, Mariusz
    DISCRETE MATHEMATICS, 2013, 313 (19) : 1843 - 1855
  • [30] PATH EXTENSIBILITY OF CONNECTED,LOCALLY 2-CONNECTED K1,3-FREE GRAPHS
    WANG Jianglu(Department of Mathematics
    Systems Science and Mathematical Sciences, 1997, (03) : 267 - 274