no. 5
Some degree conditions for 𝒫 ≥ k -factor covered graphs
RAIRO. Operations Research, Tome 55 (2021) no. 5, pp. 2907-2913

A spanning subgraph of a graph G is called a path-factor of G if its each component is a path. A path-factor is called a 𝒫$$-factor of G if its each component admits at least k vertices, where k ≥ 2. (Zhang and Zhou, Discrete Math. 309 (2009) 2067–2076) defined the concept of 𝒫$$-factor covered graphs, i.e., G is called a 𝒫$$-factor covered graph if it has a 𝒫$$-factor covering e for any e∈ E(G). In this paper, we firstly obtain a minimum degree condition for a planar graph being a 𝒫≥2-factor and 𝒫≥3-factor covered graph, respectively. Secondly, we investigate the relationship between the maximum degree of any pairs of non-adjacent vertices and 𝒫$$-factor covered graphs, and obtain a sufficient condition for the existence of 𝒫≥2-factor and 𝒫≥3-factor covered graphs, respectively.

DOI : 10.1051/ro/2021140
Classification : 05C70, 05C38
Keywords: Graph, 𝒫≥2-factor covered graph, 𝒫≥3-factor covered graph, planar graph, Minimum degree 
@article{RO_2021__55_5_2907_0,
     author = {Dai, Guowei and Zhang, Zan-Bo and Hang, Yicheng and Zhang, Xiaoyan},
     title = {Some degree conditions for $\mathcal{P}_{\ge k}$-factor covered graphs},
     journal = {RAIRO. Operations Research},
     pages = {2907--2913},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     number = {5},
     doi = {10.1051/ro/2021140},
     mrnumber = {4322047},
     zbl = {1483.05130},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2021140/}
}
TY  - JOUR
AU  - Dai, Guowei
AU  - Zhang, Zan-Bo
AU  - Hang, Yicheng
AU  - Zhang, Xiaoyan
TI  - Some degree conditions for $\mathcal{P}_{\ge k}$-factor covered graphs
JO  - RAIRO. Operations Research
PY  - 2021
SP  - 2907
EP  - 2913
VL  - 55
IS  - 5
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2021140/
DO  - 10.1051/ro/2021140
LA  - en
ID  - RO_2021__55_5_2907_0
ER  - 
%0 Journal Article
%A Dai, Guowei
%A Zhang, Zan-Bo
%A Hang, Yicheng
%A Zhang, Xiaoyan
%T Some degree conditions for $\mathcal{P}_{\ge k}$-factor covered graphs
%J RAIRO. Operations Research
%D 2021
%P 2907-2913
%V 55
%N 5
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2021140/
%R 10.1051/ro/2021140
%G en
%F RO_2021__55_5_2907_0
Dai, Guowei; Zhang, Zan-Bo; Hang, Yicheng; Zhang, Xiaoyan. Some degree conditions for $\mathcal{P}_{\ge k}$-factor covered graphs. RAIRO. Operations Research, Tome 55 (2021) no. 5, pp. 2907-2913. doi: 10.1051/ro/2021140

[1] J. Akiyama and M. Kano, Factors and factorizations of graphs-a survey. J. Graph Theory. 9 (1985) 1–42. | MR | Zbl | DOI

[2] J. Akiyama, D. Avis and H. Era, On a { 1 , 2 } -factor of a graph. TRU Math. 16 (1980) 97–102. | MR | Zbl

[3] A. Amahashi and M. Kano, Factors with given components. Discrete Math. 42 (1982) 1–6. | MR | Zbl | DOI

[4] K. Ando, Y. Egawa, A. Kaneko, K. I. Kawarabayashi and H. Matsuda, Path factors in claw-free graphs. Discrete Math. 243 (2002) 195–200. | MR | Zbl | DOI

[5] J. A. Bondy and U. S. R. Murty, Graph theory with applications, NewYork-Amsterdam-Oxford, North-Holland (1982). | Zbl

[6] V. Chvátal, Tough graphs and Hamiltonian Circuits. Discrete Math. 5 (1973) 215–228. | MR | Zbl | DOI

[7] G. Dai, The existence of path-factor covered graphs, Discuss. Math. Graph Theory. DOI: 10.7151/dmgt.2353 . | MR | Zbl

[8] Y. Egawa, M. Furuya and K. Ozeki, Sufficient conditions for the existence of a path-factor which are related to odd components. J. Graph Theory 89 (2018) 327–340. | MR | Zbl | DOI

[9] A. Kaneko, 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. Combin. Theory Ser. B 88 (2003) 195–218. | MR | Zbl | DOI

[10] A. Kaneko, A. Kelmans and T. Nishimura, On packing 3-vertex paths in a graph. J. Graph Theory 36 (2001) 175–197. | MR | Zbl | DOI

[11] M. Kano, G. Y. Katona and Z. Király, Packing paths of length at least two. Discrete Math. 283 (2004) 129–135. | MR | Zbl | DOI

[12] M. Kano, C. Lee and K. Suzuki, Path and cycle factors of cubic bipartite graphs. Discuss. Math. Graph Theory 28 (2008) 551–556. | MR | Zbl | DOI

[13] K. Kawarabayashi, H. Matsuda, Y. Oda and K. Ota, Path factors in cubic graphs. J. Graph Theory 39 (2002) 188–193. | MR | Zbl | DOI

[14] M. D. Plummer, Perspectives: Graph factors and factorization: 1985–2003: A survey. Discrete Math. 307 (2007) 791–821. | MR | Zbl | DOI

[15] W. T. Tutte, The factors of graphs. Canad. J. Math. 4 (1952) 314–328. | MR | Zbl | DOI

[16] H. Wang, Path factors of bipartite graphs. J. Graph Theory 18 (1994) 161–167. | MR | Zbl | DOI

[17] D. R. Woodall, The binding number of a graph and its Anderson number. J. Combin. Theory Ser. B 15 (1973) 225–255. | MR | Zbl | DOI

[18] J. Yang, Y. Ma and G. Liu, Fractional ( g , f ) -factors in graphs. Appl. Math. J. Chinese Univ. Ser. A 16 (2001) 385–390. | MR | Zbl

[19] Q. Yu and G. Liu, Graph Factors and Matching Extensions. Higher Education Press, Beijing (2009). | MR | Zbl

[20] P. Zhang and S. Zhou, Characterizations for 𝒫≥2-factor and 𝒫≥3-factor covered graphs. Discrete Math. 309 (2009) 2067–2076. | MR | Zbl | DOI

[21] S. Zhou, Some results about component factors in graphs. RAIRO:OR 53 (2019) 723–730. | MR | Zbl | Numdam | DOI

[22] S. Zhou, J. Wu and T. Zhang, The existence of 𝒫≥3-factor covered graphs. Discuss. Math. Graph Theory 37 (2017) 1055–1065. | MR | Zbl | DOI

Cité par Sources :