Enumerating consecutive and nested partitions for graphs (Q1378295)

Consecutive and nested partitions have been extensively studied in the set-partition problem as tools with which to search efficiently for an optimal partition. The authors extend the study of consecutive and nested partitions on a set of integers to the vertex-set of a graph \(G\). A subset of vertices of \(G\) is consecutive if the subgraph it induces is connected. A partition of the vertices of \(G\) is consecutive if each part is consecutive, and it is nested if the digraph with vertices the parts of the partition and an arc from \(P\) to \(Q\) if every connected subgraph containing \(P\) contains a vertex of \(Q\), is acyclic. In this sense the partition problem on a set of integers is simply the case where the graph is a path and the number of consecutive and nested partitions was determined by \textit{F. K. Hwang} and \textit{C. L. Mallows} [J. Comb. Theory, Ser. A 70, No. 2, 323-333 (1995; Zbl 0819.05005)]. In this paper the authors determine the number of consecutive and nested partitions when the graph \(G\) is a cycle. Also given is a partial order on general graphs with respect to these numbers.