Partitioning powers of traceable or hamiltonian graphs ?
A graph G=(V,E) G = ( V , E ) is arbitrarily partitionable (AP) if for any sequence ?=(n1,,np) ? = ( n 1 ,  , n p ) of positive integers adding up to the order of G, there is a sequence of mutually disjoint subsets of V whose sizes are given by ? and which induce connected graphs. If, additionally, for given k , it is possible to prescribe l=min{k,p} l = min { k , p } vertices belonging to the first l subsets of ?, G  is said to be AP+k AP + k . The paper contains the proofs that the kth power of every traceable graph of order at least k  is AP+(k?1) AP + ( k ? 1 ) and that the kth power of every hamiltonian graph of order at least 2k  is AP+(2k?1) AP + ( 2 k ? 1 ) , and these results are tight.
hamiltonian graph traceable graph arbitrarily partitionable graph power of a graph