On minimal arbitrarily partitionable graphs

A graph G=(V,E)G=(V,E) of order n is called arbitrarily partitionable  , or AP for short, if given any sequence of positive integers n1,…,nkn1,…,nk summing up to n, we can always partition V   into subsets V1,…,VkV1,…,Vk of sizes n1,…,nkn1,…,nk, resp., inducing connected subgraphs in G. If additionally G is minimal with respect to this property, i.e. it contains no AP spanning subgraph, we call it a minimal AP-graph. It has been conjectured that such graphs are sparse, i.e., there exists an absolute constant C   such that |E|⩽Cn|E|⩽Cn for each of them. We construct a family of minimal AP-graphs which prove that C⩾1+130 (if such C exists).

► We construct an infinite family of minimal arbitrarily partitionable non-trees. ► We prove the existence of AP-graphs with arbitrarily many arbitrarily long cycles. ► We provide a lower bound for the maximum density of minimal AP-graphs.