Arbitrary partitionability of product graphs

摘要

A graph G of order n is called arbitrarily partitionable (AP, for short) if for every sequence λ=(λ1,λ2,…,λk) of positive integers such that Σi=1kλi=n, there exists a partition (V1,V2,…,Vk) of the vertex set V(G) such that |Vi|=λi, and the subgraph G[Vi] induced by Vi is connected, for all i∈[1,k]. In this paper, we mainly discuss the arbitrary partitionability of product graphs. For the Direct product of H×Cn, we study the arbitrarily partitionability for H∈{Pm,Cm,K1,m}. For the Cartesian product, we study the arbitrarily partitionability of K1,m□Pn.