Enumerating Consecutive and Nested Partitions for Graphs

We extend the study of consecutive and nested partitions on a set of integers to the vertex-set of graph. A subset of vertices is considered consecutive if the subgraph induced by the subset is connected. In this sense the partition problem on a set of integers can be treated as a special case when the graph is a line. In this paper we give the number of consecutive and nested partitions when the graph is a cycle. We also give a partial order on general graphics with respect to these numbers.