关键词: 任意可分图, 乘积图, 似星树, 可迹图

Abstract: 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.

Key words: arbitrarily partitionable graph, product graph, star-like tree, traceable graph