# The flip Markov chain for connected regular graphs

arXiv: https://arxiv.org/abs/1701.03856 · HTML: https://mlsanity.com/paper/1701.03856/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jan 2017.

## Built on by (most cited first, 3 of 3)

- [Oversquashing in GNNs through the lens of information contraction and graph expansion](https://mlsanity.com/paper/2208.03471/) (2022)
- [Over-Squashing in Graph Neural Networks: A Comprehensive survey](https://mlsanity.com/paper/2308.15568/) (2023)
- [Effects of Dropout on Performance in Long-range Graph Learning Tasks](https://mlsanity.com/paper/2502.07364/) (2025)

## Abstract (arXiv)

Mahlmann and Schindelhauer (2005) defined a Markov chain which they called k-Flipper, and showed that it is irreducible on the set of all connected regular graphs of a given degree (at least 3). We study the 1-Flipper chain, which we call the flip chain, and prove that the flip chain converges rapidly to the uniform distribution over connected 2r-regular graphs with n vertices, where n≥ 8 and r = r(n)≥ 2. Formally, we prove that the distribution of the flip chain will be within varepsilon of uniform in total variation distance after poly(n,r,log(varepsilon-1)) steps. This polynomial upper bound on the mixing time is given explicitly, and improves markedly on a previous bound given by Feder et al.(2006). We achieve this improvement by using a direct two-stage canonical path construction, which we define in a general setting. This work has applications to decentralised networks based on random regular connected graphs of even degree, as a self-stabilising protocol in which nodes spontaneously perform random flips in order to repair the network.