Enumerating the decomposable neighbors of a decomposable graph under a simple perturbation scheme

Abstract

Given a decomposable graph, we characterize and enumerate the set of pairs of vertices whose connection or disconnection results in a new graph that is also decomposable. We discuss the relevance of these results to Markov chain Monte Carlo methods that