$ P_5 $-factors in line graphs of trees

Yuan Chen; Chi Fan; Pei Sun; Yuan Chen; Chi Fan; Pei Sun

doi:10.3934/math.2026200

AIMS Mathematics

2026, Volume 11, Issue 2: 4890-4901. doi: 10.3934/math.2026200

Previous Article Next Article

Research article Special Issues

$ P_5 $-factors in line graphs of trees

Yuan Chen ¹,
Chi Fan ¹,
Pei Sun ^{2
,
,}

1.
Research Center of Nonlinear Science, School of Mathematics and Statistics, Wuhan Textile University, Wuhan 430073, China
2.
School of Mathematics, Zhengzhou University of Aeronautics, Zhengzhou 450046, China

Received: 24 December 2025 Revised: 05 February 2026 Accepted: 12 February 2026 Published: 27 February 2026
MSC : 05C38, 05C70

Let $ \mathcal{A} $ be a set of connected graphs. A graph $ G $ has an $ \mathcal{A} $-factor if $ G $ has a spanning subgraph $ H $ such that each component of $ H $ is isomorphic to one of the members in $ \mathcal{A} $. In this paper, we give a necessary and sufficient condition for the existence of $ P_5 $-factors in line graphs of trees. Then we present an algorithm to search for a $ P_5 $-factor in the line graph of a tree.
- path factor,
- line graph,
- tree,
- algorithm
Citation: Yuan Chen, Chi Fan, Pei Sun. $ P_5 $-factors in line graphs of trees[J]. AIMS Mathematics, 2026, 11(2): 4890-4901. doi: 10.3934/math.2026200

Related Papers:

Abstract

Let $ \mathcal{A} $ be a set of connected graphs. A graph $ G $ has an $ \mathcal{A} $-factor if $ G $ has a spanning subgraph $ H $ such that each component of $ H $ is isomorphic to one of the members in $ \mathcal{A} $. In this paper, we give a necessary and sufficient condition for the existence of $ P_5 $-factors in line graphs of trees. Then we present an algorithm to search for a $ P_5 $-factor in the line graph of a tree.

References

[1]	J. Akiyama, M. Kano, Factors and factorizations of graphs-a survey, J. Graph Theor., 9 (1985), 1–42. http://doi.org/10.1002/jgt.3190090103 doi: 10.1002/jgt.3190090103
[2]	A. Amahashi, M. Kano, Factors with given components, Discrete Math., 42 (1982), 1–6. https://doi.org/10.1016/0012-365X(82)90048-6 doi: 10.1016/0012-365X(82)90048-6
[3]	K. Ando, Y. Egawa, A. Kaneko, K. Kawarabayashi, H. Matsuda, Path factors in claw-free graphs, Discrete Math., 243 (2002), 195–200. http://doi.org/10.1016/S0012-365X(01)00214-X doi: 10.1016/S0012-365X(01)00214-X
[4]	J. A. Bondy, U. S. R. Murty, Graph theory with applications, London: Macmillan Press Ltd, 1976.
[5]	Y. Chen, G. Dai, Binding number and path-factor critical deleted graphs, AKCE Int. J. Graphs Comb., 19 (2022), 197–200. http://doi.org/10.1080/09728600.2022.2094299 doi: 10.1080/09728600.2022.2094299
[6]	Y. Chen, G. Dai, Z. Hu, $P_{k}$-factors in squares and line graphs of trees, Appl. Math. Comput., 458 (2023), 128244. http://doi.org/10.1016/j.amc.2023.128244 doi: 10.1016/j.amc.2023.128244
[7]	G. Dai, Z. Hu, $P_3$-Factors in the square of a tree, Graph. Combinator., 36 (2020), 1913–1925. https://doi.org/10.1007/s00373-020-02184-7 doi: 10.1007/s00373-020-02184-7
[8]	Y. Egawa, M. Furuya, The existence of a path-factor without small odd paths, Electron. J. Comb., 25 (2018), P1.40. https://doi.org/10.37236/5817 doi: 10.37236/5817
[9]	Y. Egawa, M. Furuya, Path-factors involving paths of order seven and nine, Theory and Applications of Graphs, 3 (2016), Article 5. http://doi.org/10.20429/tag.2016.030105 doi: 10.20429/tag.2016.030105
[10]	Y. Egawa, M. Furuya, K. Ozeki, Sufficient conditions for the existence of a path-factor which are related to odd components, J. Graph Theor., 89 (2018), 327–340. https://doi.org/10.1002/jgt.22253 doi: 10.1002/jgt.22253
[11]	W. Gao, W. Wang, Y. Chen, Tight bounds for the existence of path factors in network vulnerability parameter settings, Int. J. Intell. Syst., 36 (2021), 1133–1158. http://doi.org/10.1002/int.22335 doi: 10.1002/int.22335
[12]	A. Kaneko, A. Kelmans, T. Nishimura, On packing 3-vertex paths in a graph, J. Graph Theor., 36 (2001), 175–197. https://doi.org/10.1002/1097-0118(200104)36:4<175::AID-JGT1005>3.0.CO;2-T doi: 10.1002/1097-0118(200104)36:4<175::AID-JGT1005>3.0.CO;2-T
[13]	M. Kano, C. Lee, K. Suzuki, Path and cycle factors of cubic bipartite graphs, Discuss. Math. Graph Theor., 28 (2008), 551–556. http://doi.org/10.7151/dmgt.1426 doi: 10.7151/dmgt.1426
[14]	K. Kawarabayashi, H. Matsuda, Y. Oda, K. Ota, Path factors in cubic graphs, J. Graph Theor., 39 (2002), 188–193. http://doi.org/10.1002/jgt.10022 doi: 10.1002/jgt.10022
[15]	D. G. Kirkpatrick, P. Hell, On the complexity of general graph factor problems, SIAM J. Comput., 12 (1983), 601–609. http://doi.org/10.1137/0212040 doi: 10.1137/0212040
[16]	X. Li, Z. Zhang, Path-factor in the square of a tree, Graph. Combinator., 24 (2008), 107–111. https://doi.org/10.1007/s00373-008-0775-y doi: 10.1007/s00373-008-0775-y
[17]	X. Li, Z. Zhang, $P_3$-Factor in line graphs of trees, Chinese Quarterly Journal of Mathematics, 24 (2009), 333–337.
[18]	H. Liu, X. Pan, Independence number and minimum degree for path-factor critical uniform graphs, Discrete Appl. Math., 359 (2024), 153–158. http://doi.org/10.1016/j.dam.2024.07.043 doi: 10.1016/j.dam.2024.07.043
[19]	H.-A. Loeliger, J. Dauwels, J. Hu, S. Korl, L. Ping, F. R. Kschichang, The factor graph approach to model-based signal processing, Proc. IEEE, 95 (2007), 1295–1322. http://doi.org/10.1109/JPROC.2007.896497 doi: 10.1109/JPROC.2007.896497
[20]	X. Meng, B. Hao, B. Ráth, I. A. Kovács, Path percolation in quantum communication networks, Phys. Rev. Lett., 134 (2025), 030803. https://doi.org/10.1103/PhysRevLett.134.030803 doi: 10.1103/PhysRevLett.134.030803
[21]	M. D. Plummer, Graph factors and factorization: 1985-2003: a survey, Discrete Math., 307 (2007), 791–821. http://doi.org/10.1016/j.disc.2005.11.059 doi: 10.1016/j.disc.2005.11.059
[22]	W. T. Tutte, The factors of graphs, Can. J. Math., 4 (1952), 314–328. http://doi.org/10.4153/CJM-1952-028-2
[23]	X. Wu, B. Xiao, C. Wu, Y. Guo, L. Li, Factor graph based navigation and positioning for control system design: a review, Chinese J. Aeronaut., 35 (2022), 25–39. https://doi.org/10.1016/j.cja.2021.09.001 doi: 10.1016/j.cja.2021.09.001
[24]	Q. R. Yu, G. Liu, Graph factors and matching extensions, Berlin, Heidelberg: Springer, 2009. http://doi.org/10.1007/978-3-540-93952-8
[25]	H. Wang, Path factors of bipartite graphs, J. Graph Theor., 18 (1994), 161–167. http://doi.org/10.1002/jgt.3190180207 doi: 10.1002/jgt.3190180207
[26]	S. Zhou, Y. Zhang, Z. Sun, The $A_\alpha$-spectral radius for path-factors in graphs, Discrete Math., 347 (2024), 113940. http://doi.org/10.1016/j.disc.2024.113940 doi: 10.1016/j.disc.2024.113940
[27]	L. Zhu, H. M. Baskonus, W. Gao, Vulnerability variants and path factors in networks, In: Machine learning for cyber security, Cham: Springer, 2020, 1–11. https://doi.org/10.1007/978-3-030-62460-6_1

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)