Partitioning The Product Graph

A graph G is called arbitrarily partitionable(AP for short)if for any sequenceλ=(λ1,λ2,…,λp)of positive integers adding up to |V(G)|,there is a partition(V1,V2,…,Vp)of the vertex set of G such that each Vi induces a connected subgraph in G and |Vi|＝λi for i=1,2,…,p.Our main results are summarized as follows:Let S(a1,a2,…,at,b1,b2,…,bl)be a star-like tree with Δ(S)=t+l,where ai is odd,bj is even for 0≤i≤t,0≤j≤1,and a1≤a2≤at,b1≤b2≤…≤bl.We show that for an even integer n≥2 and Δ(S)≤n+1,if t≤2 or t≥3 and a3>1,then S□Pn is AP.For odd integer n≥2,if Δ(S)≤n+l and t≤2,then S□Pn is AP;if Δ(S)≤n+1 and t≥3,then S□Pn is not AP.Let K1,t be a star with maximum degree is t.We show that if t≤6,n≥t-1,then strong product K1,t(?)Pn is AP.