Partitioning the Cartesian product of a tree and a cycle

摘要

Let G=(V,E) be a graph of order n, and λ=(λ1,λ2,…,λp) a sequence of positive integers. The sequence λ is admissible for G if λ1+⋯+λp=n. Such an admissible sequence λ is said to be realizable in G if there exists a partition (V1,V2,…,Vp) of the vertex set V such that Vi induces a connected subgraph of order ni in G for each i. If every admissible sequence is realizable in G, then we say that G is arbitrarily partitionable (AP, for short). We show that if a tree T of maximum degree at most n+1 has a path containing all the vertices of degree n+1, then T□Cn has a Hamiltonian path. In particular, for any caterpillar T with maximum degree at most n+1, T□Cn is AP. In addition, if T is a caterpillar with Δ(T)≥n+4, then T□Cn is not AP. For the cases n+2≤Δ(T)≤n+3, we present some sufficient conditions for a caterpillar T such that T□Cn is AP.