On the path partition of graphs

• Autorzy: Kouider Mekkia , Zamime Mohamed

Identyfikatory

DOI

10.7494/OpMath.2023.43.6.829

• Języki publikacji: EN

Abstrakty

EN

Let G be a graph of order n. The maximum and minimum degree of G are denoted by Δ and δ, respectively. The path partition number μ(G) of a graph G is the minimum number of paths needed to partition the vertices of G. Magnant, Wang and Yuan conjectured that [formula]. In this work, we give a positive answer to this conjecture, for Δ ≥ 2δ.

Słowa kluczowe

EN

path; partition; graphs

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2023
• Tom: Vol. 43, no. 6
• Strony: 829--839
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Kouider Mekkia

• University Paris Sud, France

autor

Zamime Mohamed

• University Yahia Fares of Medea, Department of Technology, Mathematics Laboratory and its Applications, Medea, Algeria

Bibliografia

• [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] 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] V. Gruslys, S. Letzter, Cycle partitions of regular graphs, arXiv:1808.00851.
• [4] J. Han, On vertex-disjoint paths in regular graphs, Electron. J. Combin. 25 (2018), no. 2, #P2.12.
• [5] M. Kouider, Neighborhood and covering vertices by cycles, Combinatorica 20 (2000), no. 2, 219–226.
• [6] M. Kouider, Covering vertices by cycles, J. Graph Theory 18 (1994), no. 8, 757–776.
• [7] M. Kouider, Z. Lonc, Covering cycles and k-term degree sums, Combinatorica 16 (1996), 407–412.
• [8] J. Li, G. Steiner, Partitioning a bipartite graph into vertex-disjoint paths, Ars Combin. 81 (2006), 161–173.
• [9] Ch. Lu, Q. Zhou, Path covering number and L(2, 1)-labeling number of graphs, Discrete Appl. Math. 161 (2013), 2062–2074.
• [10] C. Magnant, D.M. Martin, A note on the path cover number of regular graphs, Australas. J. Combin. 43 (2009), 211–217.
• [11] C. Magnant, H. Wang, Path partition of almost regular graphs, Australas. J. Combin. 64 (2016), 334–340.
• [12] P. Manuel, Revisiting path-type covering and partitioning problems, (2018), hal-01849313.
• [13] O. Ore, Arc coverings of graphs, Ann. Mat. Pura Appl. 55 (1961), no. 4, 315–321.
• [14] B. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996), no. 3, 277–295.
• [15] G. Yu, Covering 2-connected 3-regular graphs by disjoint paths, J. Graph Theory 18 (2018), no. 3, 385–401.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023)