Sufficient conditions for graphs with $\{P_2,P_5\}$-factors.

Dai, Guowei; Hang, Yicheng; Zhang, Xiaoyan; Zhang, Zan-Bo; Wang, Wenqi

RAIRO. Operations Research, Tome 56 (2022) no. 4, pp. 2895-2901

For a graph G, a spanning subgraph F of G is called an {P₂, P₅}-factor if every component of F is isomorphic to P₂ or P₅, where P$$ denotes the path of order k. It was proved by Egawa and Furuya that if G satisfies 3c₁ (G − S) + 2c₃ (G − S) ≤ 4|S| + 1 for all S ⊆ V(G), then G has a {P₂, P₅}-factor, where c$$ (G − S) denotes the number of components of G − S with order k. By this result, we give some other sufficient conditions for a graph to have a {P₂, P₅}-factor by various graphic parameters such as toughness, binding number, degree sums, etc. Moreover, we obtain some regular graphs and some K$$-free graphs having {P₂, P₅}-factors.

Classification : 05C70, 05C38
Keywords: {$$₂, $$₅}-factor, degree sum, binding number, toughness, regular graph, $$_(1,r)-free graph

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

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

[3] 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 | DOI

[4] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications. North-Holland, New York-Amsterdam-Oxford (1982).

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

[6] G. Dai, The existence of path-factor covered graphs. Discuss. Math. Graph Theory (2020). DOI: . | DOI | MR

[7] G. Dai, Remarks on component factors in graphs. RAIRO: Oper. Res. 56 (2022) 721–730. | MR | Zbl | Numdam | DOI

[8] G. Dai and Z. Hu, $P_3$-factors in the square of a tree. Graphs Comb. 36 (2020) 1913–1925. | MR | DOI

[9] G. Dai, Z. Zhang, Y. Hang and X. Zhang, Some degree conditions for $P_{\ge 3}$-factor covered graphs. RAIRO: Oper. Res. 55 (2021) 2907–2913. | MR | Zbl | Numdam | DOI

[10] Y. Egawa and M. Furuya, The existence of a path-factor without small odd paths. Electron. J. Comb. 25 (2018) 1–40. | MR

[11] Y. Egawa and M. Furuya, Path-factors involving paths of order seven and nine. Theory App. Graphs 3 (2016). DOI: . | DOI | MR

[12] 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 | DOI

[13] 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. Comb. Theory Ser. B 88 (2003) 195–218. | MR | DOI

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

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

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

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

[18] M. Loebl and S. Poljak, Efficient subgraph packing. J. Comb. Theory Ser. B 59 (1993) 106–121. | MR | DOI

[19] M. D. Plummer, Perspectives: graph factors and factorization: 1985–2003: a survey. Discrete Math. 307 (2007) 791–821. | MR | DOI

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

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

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

[23] P. Zhang and S. Zhou, Characterizations for $P_{\ge 2}$-factor and $P_{\ge 3}$-factor covered graphs. Discrete Math. 309 (2009) 2067–2076. | MR | DOI