论文标题
在图的路径分区上
On the path partition of graphs
论文作者
论文摘要
令$ g $为订单$ n $的图。 $ g $的最高和最低度分别用$δ$和$δ$表示。 图$ g $的\ emph {路径分区} $μ（g）$是划分$ g $的顶点所需的最小路径数。 Magnant, Wang and Yuan conjectured that $μ(G)\leq \max \left \{ \frac{n}{δ+1}, \frac{\left( Δ-δ\right) n}{\left( Δ+δ\right) }\right \} .$ In this work, we give a positive answer to this conjecture, for $ δ\ geq2δ$。\ medskip \ end {amperpt {abract}
Let $G$ be a graph of order $n$. The maximum and minimum degree of $G$ are denoted by $Δ$ and $δ$ respectively. The \emph{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 $μ(G)\leq \max \left \{ \frac{n}{δ+1}, \frac{\left( Δ-δ\right) n}{\left( Δ+δ\right) }\right \} .$ In this work, we give a positive answer to this conjecture, for $ Δ\geq 2 δ$.\medskip \end{abstract}
