TY  - JOUR
ID  - Kouider2023
LB  - Kouider2023
AU  - Kouider, Mekkia
AU  - Zamime, Mohamed
TI  - On the path partition of graphs
ST  - On the path partition of graphs
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2023
VL  - 43
IS  - 6
SP  - 829
EP  - 839
DO  - https://doi.org/10.7494/OpMath.2023.43.6.829
UR  - https://doi.org/10.7494/OpMath.2023.43.6.829
AB  - 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\).
KW  - path
KW  - partition
SN  - 1232-9274
ER  -