  Consider observations $y_1,\dots,y_n$ on nodes of a connected graph, where
the $y_i$ independently come from $N(\theta_i, \sigma^2)$ distributions and an
unknown partition divides the $n$ observations into blocks. One well-studied
class of change point problems assumes the means $\theta_i$ are equal for all
nodes within contiguous blocks of a simple graph of sequential observations;
both frequentist and Bayesian approaches have been used to estimate the
$\theta_i$ and the change points of the underlying partition. This paper
examines a broad class of change point problems on general connected graphs in
which a regression model is assumed to apply within each block of the partition
of the graph. This general class also supports multivariate change point
problems. We use Bayesian methods to estimate change points or block boundaries
of the underlying partition. This paper presents the methodology for the
general class of change point problems and develops new algorithms for
implementation via Markov Chain Monte Carlo. The paper concludes with
simulations and real data examples to demonstrate application of the
methodology on a wide range of problems.
