REMARKS ON COMPONENT FACTORS IN Κ1,r -FREE GRAPHS

被引:1
作者
Dai, Guowei [1 ]
Zhang, Zan-Bo [2 ,3 ]
Zhang, Xiaoyan [4 ,5 ]
机构
[1] Nanjing Forestry Univ, Coll Sci, Nanjing 210037, Jiangsu, Peoples R China
[2] Guangdong Univ Finance & Econ, Sch Stat & Math, Guangzhou 510630, Guangdong, Peoples R China
[3] Guangdong Univ Finance & Econ, Inst Artificial Intelligence & Deep Learning, Guangzhou 510630, Guangdong, Peoples R China
[4] Nanjing Normal Univ, Sch Math Sci, Nanjing 210023, Jiangsu, Peoples R China
[5] Nanjing Normal Univ, Inst Math, Nanjing 210023, Jiangsu, Peoples R China
基金
中国国家自然科学基金;
关键词
Minimum degree; Kappa(1; r)-free; S-n-factor; P->= k-factor; P->= k-factor covered graph; PATH-FACTOR; EXISTENCE; LENGTH;
D O I
10.1051/ro/2023042
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
An F-factor is a spanning subgraph Eta such that each connected component of Eta is isomorphic to some graph in F. We use P-k and Kappa(1,r) to denote the path of order k and the star of order r + 1, respectively. In particular, Eta is called a {P-2,P3}-factor of G if F = {P-2,P-3}; Eta is called a P >= k-factor of G if F = {P-k,Pk+1,...}, where k >= 2; Eta is called an S-n-factor of.. if F = {P-2,P-3, Kappa(1,3),...,..Kappa(1,n)}, where n >= 2. A graph.. is called a P >= k-factor covered graph if there is a P >= k-factor of G including e for any e is an element of E (G). We call a graph G is K-1,K-r -free if.. does not contain an induced subgraph isomorphic to K-1,K-r. In this paper, we give a minimum degree condition for the K-1,K-r-free graph with an S-n-factor and the. K-1,K-r-free graph with a P >= 3-factor, respectively. Further, we obtain sufficient conditions for K-1,K-r-free graphs to be P >= 2-factor P >==3-factor or {P-2,P-3}-factor covered graphs. In addition, examples show that our results are sharp.
引用
收藏
页码:837 / 846
页数:10
相关论文
共 33 条
[1]  
Akiyama J, 2011, LECT NOTES MATH, V2031, P1, DOI 10.1007/978-3-642-21919-1
[2]   FACTORS AND FACTORIZATIONS OF GRAPHS - A SURVEY [J].
AKIYAMA, J ;
KANO, M .
JOURNAL OF GRAPH THEORY, 1985, 9 (01) :1-42
[3]  
Akiyama J., 1980, TRU Math, V16, P97
[4]   ON FACTORS WITH GIVEN COMPONENTS [J].
AMAHASHI, A ;
KANO, M .
DISCRETE MATHEMATICS, 1982, 42 (01) :1-6
[5]  
Bondy J. A., 1976, Graph theory with applications
[6]   Binding number and path-factor critical deleted graphs [J].
Chen, Yuan ;
Dai, Guowei .
AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2022, 19 (03) :197-200
[7]   ON 2-MATCHING COVERED GRAPHS AND 2-MATCHING DELETED GRAPHS [J].
Dai, Guowei .
RAIRO-OPERATIONS RESEARCH, 2022, 56 (05) :3667-3674
[8]   Sufficient conditions for graphs with {P2, P5}-factors [J].
Dai, Guowei ;
Hang, Yicheng ;
Zhang, Xiaoyan ;
Zhang, Zan-Bo ;
Wang, Wenqi .
RAIRO-OPERATIONS RESEARCH, 2022, 56 (04) :2895-2901
[9]   REMARKS ON COMPONENT FACTORS IN GRAPHS [J].
Dai, Guowei .
RAIRO-OPERATIONS RESEARCH, 2022, 56 (02) :721-730
[10]   THE EXISTENCE OF PATH-FACTOR COVERED GRAPHS [J].
Dai, Guowei .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2023, 43 (01) :5-16