Opuscula Math. 43, no. 6 (2023), 829-839
https://doi.org/10.7494/OpMath.2023.43.6.829
Opuscula Mathematica
On the path partition of graphs
Abstract. Let \(G\) be a graph of order \(n\). The maximum and minimum degree of \(G\) are denoted by \(\Delta\) and \(\delta\), respectively. The path partition number \(\mu(G)\) of a graph \(G\) is the minimum number of paths needed to partition the vertices of \(G\). Magnant, Wang and Yuan conjectured that \[\mu(G)\leq\max \left\{\frac{n}{\delta+1},\frac{(\Delta-\delta)n}{\Delta+\delta}\right\}.\] In this work, we give a positive answer to this conjecture, for \(\Delta\geq 2\delta\).
Keywords: path, partition.
Mathematics Subject Classification: 05C20.
- M. Chen, J. Li, L. Wang, L. Zhang, On partitioning simple bipartite graphs in vertex-disjoint paths, Southeast Asian Bull. Math. 31 (2007), no. 2, 225-230.
- H. Enomoto, K. Ota, Partitions of a graph into paths with prescribed endvertices and lengths, J. Graph Theory 34 (2000), no. 2, 163-169.
- V. Gruslys, S. Letzter, Cycle partitions of regular graphs, arXiv:1808.00851.
- J. Han, On vertex-disjoint paths in regular graphs, Electron. J. Combin. 25 (2018), no. 2, #P2.12.
- M. Kouider, Neighborhood and covering vertices by cycles, Combinatorica 20 (2000), no. 2, 219-226.
- M. Kouider, Covering vertices by cycles, J. Graph Theory 18 (1994), no. 8, 757-776.
- M. Kouider, Z. Lonc, Covering cycles and \(k\)-term degree sums, Combinatorica 16 (1996), 407-412.
- J. Li, G. Steiner, Partitioning a bipartite graph into vertex-disjoint paths, Ars Combin. 81 (2006), 161-173.
- Ch. Lu, Q. Zhou, Path covering number and \(L(2, 1)\)-labeling number of graphs, Discrete Appl. Math. 161 (2013), 2062-2074.
- C. Magnant, D.M. Martin, A note on the path cover number of regular graphs, Australas. J. Combin. 43 (2009), 211-217.
- C. Magnant, H. Wang, Path partition of almost regular graphs, Australas. J. Combin. 64 (2016), 334-340.
- P. Manuel, Revisiting path-type covering and partitioning problems, (2018), hal-01849313.
- O. Ore, Arc coverings of graphs, Ann. Mat. Pura Appl. 55 (1961), no. 4, 315-321.
- B. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996), no. 3, 277-295.
- G. Yu, Covering 2-connected 3-regular graphs by disjoint paths, J. Graph Theory 18 (2018), no. 3, 385-401.
- Mekkia Kouider (corresponding author)
- University Paris Sud, France
- Mohamed Zamime
- University Yahia Fares of Medea, Department of Technology, Mathematics Laboratory and its Applications, Medea, Algeria
- Communicated by Gyula O.H. Katona.
- Received: 2023-01-17.
- Revised: 2023-06-27.
- Accepted: 2023-07-07.
- Published online: 2023-07-22.
