More Aspects of Arbitrarily Partitionable Graphs

Abstract

A graph G of order n is arbitrarily partitionable (AP) if, for every sequence (n1, . . ., np) partitioning n, there is a partition (V1, . . ., ,Vp) of V (G) such that G[Vi] is a connected ni-graph for i = 1, . . ., p. The property of being AP is related to other well-known graph notions, such as perfect matchings and Hamiltonian cycles, with which it shares several properties. This work is dedicated to studying two aspects behind AP graphs.

Keywords

• arbitrarily partitionable graphs
• partition into connected subgraphs
• hamiltonicity
• 05c15
• 05c40
• 05c69
• 68r10