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 \emph{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)\le \max \left\{\frac{n}{\delta +1},\frac{\left(\Delta -\delta \right)n}{\left(\Delta +\delta \right)}\right\}.$ In this work, we give a positive answer to this conjecture, for $\Delta \ge 2\delta$.\medskip \end{abstract}

13 pages,3 figures