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

Arbitrarily Partitionable Product Graph ofStar-Like Tree and Path

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

Let S=S(a 1,a 2,…,a t,b 1,b 2,…,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 S■P l of a star-like tree S and a path P l is arbi trarily partitionable graph.We give some sufficient conditions for S such that S■P l is not arbitrarily partitionable graph by contradicti on and the method of graphs without perfect matching.Secondly,by analyzing the Hamiltonian property of graphs S■P l and using arbitrary partition of s tar-like trees,we give some sufficient conditions for S such that S■P l is arbitrarily partitionable graph.The results show that if t=1 and s≤2,then S P l is arbitrarily partitionable graph;if t≥2 or t=0,or t=1,s≥3,b 1=b 2=…=b s,t+s≥l+2,then S■P l is not arbitrarily partitionable graph.