DIMACS TR: 93-15
Enumerating Consecutive and Nested Partitions for Graphs
Authors: F. K. Hwang and G. J. Chang
ABSTRACT
We extend the study of consecutive and nested partitions on a set of
integers to the vertex-set of a 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 graphs with respect to these numbers.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-15.ps
DIMACS Home Page