似星树与路的乘积图的任意可分性

设似星树S=S(a₁,a₂,…,a_t,b₁,b₂,…,b_s), 其中a_i(1≤i≤t)是奇数, b_j(1≤j≤s)是偶数. 首先, 讨论似星树S与路P_l的乘积图SPl在t和s不同取值下是否为任意可分图, 并用图不含完美匹配的方法和反证法给出其不是任意可分图的充分条件; 其次, 分析图SP_l的Hamilton性, 并用似星树的任意可分性给出图为任意可分图的充分条件. 结果表明, 当t=1且s≤2时, 图SP_l是任意可分图; 当t≥2或t=0, 或者t=1, s≥3, b₁=b₂=…=b_s, t+s≥l+2时, 图SP_l均不是任意可分图.

Arbitrarily Partitionable Product Graph of Star-Like Tree and Path

Let S=S(a₁,a₂,…,a_t,b₁,b₂,…,b_s) be a star-like tree, where a_i is odd, b_j is even for 1≤i≤t, 1≤j≤s. Firstly, under different values of t and s, we discuss whether the product graph SP of a star-like tree S and a path P_l is arbitrarily partitionable graph. We give some sufficient conditions for S such that SP is not arbitrarily partitionable graph by contradiction and the method of graphs without perfect matching. Secondly, by analyzing the Hamiltonian property of graphs SP_l and using arbitrary partition of star-like trees, we give some sufficient conditions for S such that SP is arbitrarily partitionable graph. The results show that if t=1 and s≤2, then SP_l is arbitrarily partitionable graph; if t≥2 or t=0, or t=1, s≥3, b₁=b₂=…=b_s, t+s≥l+2, then SP_l is not arbitrarily partitionable graph.