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$.