一个关于树图的P_3-因子存在性的充要条件

A Necessary and Sufficient Condition for the Existence of P_3-factor for Trees

图G存在pn-因子,如果G有一个全部由Pn构成的支撑子图H。给出关于树图T存在Pn-因子的一个充分必要条件,并给予证明。类比Tutte定理,得到了树图T有一个P3-因子充要条件是对任意v∈V(T)有O1(T-v)+2O(2T-v)=2,其中O(iT-v)表示T-v中阶数模3余i的分支数。在此基础上,探讨了一般图G存在P3-因子的条件。

Graph G has a Pn-factor, if G has a spanning subgraph H,of which each component is Pn. A necessary and sufficient condition for the existence of Pn-factor for trees is given and proved. It is found that a tree T has a P3-factor if and only if O1 （T-v） ＋2O2 （T-v） =2 for all v ∈ V （T）, where Oi （T-v） is number of components which order equal i （rood 3） of T-v. Moreover, the condition for existence of P3-factor for graphs G is studied.