THE EXISTENCE OF PATH-FACTOR COVERED GRAPHS

被引：16

作者：

Dai, Guowei ^{[1
]}

机构：

[1] Cent China Normal Univ, Fac Math & Stat, Luoyu Rd 152, Wuhan 430079, Hubei, Peoples R China

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2023年 / 43卷 / 01期

关键词：

path-factor; P >= 2-factor covered graph; P >=; 3-factor covered graph; claw-free graph; isolated toughness; LENGTH;

D O I：

10.7151/dmgt.2353

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A spanning subgraph H of a graph G is called a P>k-factor of G if every component of H is isomorphic to a path of order at least k, where k > 2. A graph G is called a P>k-factor covered graph if there is a P>k-factor of G covering e for any e E E(G). In this paper, we obtain two special classes of P>2-factor covered graphs. We also obtain two special classes of P>3-factor covered graphs. Furthermore, it is shown that these results are all sharp.

引用

页码：5 / 16

页数：12

共 21 条

[1] FACTORS AND FACTORIZATIONS OF GRAPHS - A SURVEY [J].

AKIYAMA, J ;

KANO, M .

JOURNAL OF GRAPH THEORY, 1985, 9 (01) :1-42

[2]

Akiyama J., 1980, TRU Math, V16, P97

[3] ON FACTORS WITH GIVEN COMPONENTS [J].

AMAHASHI, A ;

KANO, M .

DISCRETE MATHEMATICS, 1982, 42 (01) :1-6

[4] 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

[5] 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

[6]

Bondy J. A., 1976, Graph theory with applications

[7]

Chvatal V., 1973, Discrete Mathematics, V5, P215, DOI 10.1016/0012-365X(73)90138-6

[8] Sufficient conditions for the existence of a path-factor which are related to odd components [J].

Egawa, Yoshimi ;

Furuya, Michitaka ;

Ozeki, Kenta .

JOURNAL OF GRAPH THEORY, 2018, 89 (03) :327-340

[9] 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

[10]

Kaneko A, 2001, J GRAPH THEOR, V36, P175, DOI 10.1002/1097-0118(200104)36:4<175::AID-JGT1005>3.0.CO

← 1 2 3 →