Opuscula Mathematica
Opuscula Math. 43, no. 6 (2023), 829-839

On the path partition of graphs

Mekkia Kouider
Mohamed Zamime
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.
Full text (pdf)
References ▼
  1. [1] 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.
  2. [2] H. Enomoto, K. Ota, Partitions of a graph into paths with prescribed endvertices and lengths, J. Graph Theory 34 (2000), no. 2, 163-169.
  3. [3] V. Gruslys, S. Letzter, Cycle partitions of regular graphs, arXiv:1808.00851.
  4. [4] J. Han, On vertex-disjoint paths in regular graphs, Electron. J. Combin. 25 (2018), no. 2, #P2.12.
  5. [5] M. Kouider, Neighborhood and covering vertices by cycles, Combinatorica 20 (2000), no. 2, 219-226.
  6. [6] M. Kouider, Covering vertices by cycles, J. Graph Theory 18 (1994), no. 8, 757-776.
  7. [7] M. Kouider, Z. Lonc, Covering cycles and \(k\)-term degree sums, Combinatorica 16 (1996), 407-412.
  8. [8] J. Li, G. Steiner, Partitioning a bipartite graph into vertex-disjoint paths, Ars Combin. 81 (2006), 161-173.
  9. [9] Ch. Lu, Q. Zhou, Path covering number and \(L(2, 1)\)-labeling number of graphs, Discrete Appl. Math. 161 (2013), 2062-2074.
  10. [10] C. Magnant, D.M. Martin, A note on the path cover number of regular graphs, Australas. J. Combin. 43 (2009), 211-217.
  11. [11] C. Magnant, H. Wang, Path partition of almost regular graphs, Australas. J. Combin. 64 (2016), 334-340.
  12. [12] P. Manuel, Revisiting path-type covering and partitioning problems, (2018), hal-01849313.
  13. [13] O. Ore, Arc coverings of graphs, Ann. Mat. Pura Appl. 55 (1961), no. 4, 315-321.
  14. [14] B. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996), no. 3, 277-295.
  15. [15] G. Yu, Covering 2-connected 3-regular graphs by disjoint paths, J. Graph Theory 18 (2018), no. 3, 385-401.
About the authors ▼
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
About the article ▼
Communicated by Gyula O.H. Katona.
Received: 2023-01-17.
Revised: 2023-06-27.
Accepted: 2023-07-07.
Published online: 2023-07-22.
Cite this article as ▼
Mekkia Kouider, Mohamed Zamime, On the path partition of graphs, Opuscula Math. 43, no. 6 (2023), 829-839, https://doi.org/10.7494/OpMath.2023.43.6.829.
Download this article's citation as: