Degree conditions for path-factor critical deleted or covered graphs

被引:1
作者
Liu, Hongxia [1 ]
机构
[1] Yantai Univ, Sch Math & Informat Sci, Yantai 264005, Shandong, Peoples R China
关键词
Graph; Degree condition; P(=)3-factor; (P-=3n)-factor critical deleted graph; n)-factor critical covered graph; COMPONENT; LENGTH; NUMBER;
D O I
10.1051/ro/2023078
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
A path-factor of a graph ?? is a spanning subgraph of ?? whose components are paths. A ??=??-factor of a graph ?? is a path-factor of ?? whose components are paths with at least ?? vertices, where ?? is an integer with ?? = 2. A graph ?? is ??=??-factor covered if for any ?? ? ??(??), ?? admits a ??=??-factor including ??. A graph ?? is (??=??, ??)-factor critical deleted if for any ?? ? ?? (??) with |??| = ?? and any ?? ? ??(?? - ??), ?? - ?? - ?? has a ??=??-factor. A graph ?? is (??=??, ??)-factor critical covered if for any ?? ? ?? (??) with |??| = ??, ?? - ?? is a ??=??-factor covered graph. In this paper, we verify that (i) an (?? + ?? + 2)-connected graph ?? of order ?? with ?? = 4?? + ?? + 7 is (??=3, ??)-factor critical deleted if max{????(??1), ??(??)(??(2)), . . . , ????(??(2??+1))} =( ??+2??) /(3) for any independent set {??1, ??2, . . . , ??2??+1} of ??, where ?? and ?? are two nonnegative integers with ?? = 1; (ii) an (?? + ?? + 1)-connected graph ?? of order ?? with ?? = 4?? + ?? + 5 is (??=3, ??)-factor critical covered if max{????(??1), ????(??2), . . . , ????(??2??+1)} =( ??+2??+2)/(3) for any independent set {??(1), ??(2), . . . , ??(2??+1)} of ??, where ?? and ?? are two nonnegative integers with ?? = 1.
引用
收藏
页码:1443 / 1451
页数:9
相关论文
共 27 条
[1]   Path factors in claw-free graphs [J].
Ando, K ;
Egawa, Y ;
Kaneko, A ;
Kawarabayashi, K ;
Matsuda, H .
DISCRETE MATHEMATICS, 2002, 243 (1-3) :195-200
[2]   Partitioning vertices of 1-tough graphs into paths [J].
Bazgan, C ;
Harkat-Benhamdine, A ;
Li, H ;
Wozniak, M .
THEORETICAL COMPUTER SCIENCE, 2001, 263 (1-2) :255-261
[3]   A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two [J].
Kaneko, A .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2003, 88 (02) :195-218
[4]   Packing paths of length at least two [J].
Kano, M ;
Katona, GY ;
Király, Z .
DISCRETE MATHEMATICS, 2004, 283 (1-3) :129-135
[5]   Component factors with large components in graphs [J].
Kano, M. ;
Lu, Hongliang ;
Yu, Qinglin .
APPLIED MATHEMATICS LETTERS, 2010, 23 (04) :385-389
[6]  
Kano M., 2008, Discuss. Math. Graph Theory, P551
[7]   Sun toughness and path-factor uniform graphs [J].
Liu, Hongxia .
RAIRO-OPERATIONS RESEARCH, 2022, 56 (06) :4057-4062
[8]   Toughness, binding number and restricted matching extension in a graph [J].
Plummer, Michael D. ;
Saito, Akira .
DISCRETE MATHEMATICS, 2017, 340 (11) :2665-2672
[9]   Research on Fractional Critical Covered Graphs [J].
Wang, S. ;
Zhang, W. .
PROBLEMS OF INFORMATION TRANSMISSION, 2020, 56 (03) :270-277
[10]   Exploring Factors Affecting Choice of Currency for Pricing and Settlement in International Trade [J].
Wang, Shanshan ;
Zhang, Li ;
Zhan, Boxuan .
PROCEEDINGS OF THE 6TH INTERNATIONAL CONFERENCE ON E-COMMERCE, E-BUSINESS AND E-GOVERNMENT, ICEEG 2022, 2022, :229-236