Partitioning powers of traceable or hamiltonian graphs

详细信息    查看全文

• 作者：Olivier Baudon ; Julien Bensmail ; Jakub Przyby艂o ; Mariusz Wo藕niak
• 关键词：Arbitrarily partitionable graph ; Power of a graph ; Hamiltonian graph ; Traceable graph
• 刊名：Theoretical Computer Science
• 出版年：6 February, 2014
• 年：2014
• 卷：520
• 期：Complete
• 页码：133-137
• 全文大小：199 K

文摘

A graph is arbitrarily partitionable (AP) if for any sequence 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 vertices belonging to the first l subsets of 蟿, G is said to be .

The paper contains the proofs that the kth power of every traceable graph of order at least k is and that the kth power of every hamiltonian graph of order at least 2k is , and these results are tight.