Partitioning powers of traceable or hamiltonian graphs

A graph G =(V,E) is arbitrarily partitionable (AP) if for any sequence τ =(n1,...,np) 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 t...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2014-02, Vol.520
Main Authors: Baudon, Olivier, Bensmail, Julien, Przybylo, Jakub, Woźniak, Mariusz
Format: Article
Language:English
Subjects:
Computer Science
Discrete Mathematics
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A graph G =(V,E) is arbitrarily partitionable (AP) if for any sequence τ =(n1,...,np) 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} vertices belonging to the first l subsets of τ, G is said to be AP+k. The paper contains the proofs that the kth power of every traceable graph of order at least k is AP + (k − 1) and that the kth power of every hamiltonian graph of order at least 2k is AP + (2k − 1), and these results are tight.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2013.10.016