Starting with a given simple, directed Graph G, I define a two-edge swap as:

  1. select two edges u->v and x->y such that (u!=x) and (v!=y) and (u!=y) and (x!=v)
  2. delete the two edges u->v and x->y
  3. add edges u->y and x->v

Is it guaranteed that I can reach any simple directed graph with the original (in- and out-) degree sequence in some finite number of 2-edge swaps?

If we need some sort of 3-edge swaps, what are they?

Background: I intend to use this as MCMC steps to sample random graphs, but over at the Networkx Developer site, there is a discussion that Theorem 7 of the paper P Erdos et al., "A simple Havel–Hakimi type algorithm to realize graphical degree sequences of directed graphs", Combinatorics 2010 implies that we need 3-edge swaps to sample the whole space.


On page 6 of the linked paper, a triple swap is defined. Basically, you transform $v_n \rightarrow v_k \rightarrow v_i \rightarrow v_m$ into $v_n \rightarrow v_i \rightarrow v_k \rightarrow v_m$.

enter image description here


The question is whether a triple swap is necessary or not. One of the examples in the paper is the directed cycle between three nodes (i->j), (j->k), (k->i). Obviously, another graph with the same degree sequence is the one in which all directions are reversed: (i <- j), (j <- k), (k <- i). It is, however, not possible to get from the first to the second graph if you do not allow for self-loops: there are no two edges whose swap is allowed under this condition. At first I thought that there cannot be an example for this is in larger graphs but actually there are graphs of infinite size with the same problem (under the condition of no multiple edges and self-loops): again, start with the directed triangle; add any number of nodes that are connected to all other nodes by bi-directional edges. Thus, the only edges that are flexible are the ones in the triangle and again, all of their edges can be reversed to result in a graph with the same degree sequences but no sequence of edge-swaps can achieve it.

It is obvious that the family of graphs described here is very much constrained but there may be others with similar problems. Thus: there are directed graphs which need the triple-swap s.t. all graphs with the same degree sequences but without multiple edges and self-loops can be samples u.a.r.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.