  The study of sorting permutations by block interchanges has recently been
stimulated by a phenomenon observed in the genome maintenance of certain
ciliate species. The result was the identification of a block interchange
operation that applies only under certain constraints. Interestingly, this
constrained block interchange operation can be generalized naturally to simple
graphs and to an operation on square matrices. This more general context
provides numerous techniques applicable to the original context. In this paper
we consider the more general context, and obtain an enumeration, in closed
form, of all simple graphs on n vertices that are ``sortable" by the graph
analogue of the constrained version of block interchanges. We also obtain
asymptotic results on the proportion of graphs on n vertices that are so
sortable.
