6 - Interchange Graphs

Summary

In this chapter we study the interchange graph G(R, S) of a nonempty class A(R, S) of (0,1)-matrices with row sum vector R and column sum vector S, and investigate such graphical parameters as the diameter and connectivity. We also study the Δ-interchange graph of a nonempty class Τ (R) of tournament matrices with row sum vector R and show that it has a very special structure; in particular that it is a bipartite graph. In the final section we discuss how to generate uniformly at random a tournament matrix in a nonempty class Τ (R) and a matrix in a nonempty class A(R, S).

Diameter of Interchange Graphs G(R, S)

We assume throughout this section that R = (r₁, r₂, …, r_m) and S = (s₁, s₂, …, s_n) are nonnegative integral vectors for which the class A(R, S) is nonempty.

The vertex set of the interchange graph G(R, S), as defined in Section 3.2, is the set A(R, S). Two matrices in A(R, S) are joined by an edge in G(R, S) provided A differs from B by an interchange, equivalently, A – B is an interchange matrix. By Theorem 3.2.3, given matrices A and B in A(R, S), a sequence of interchanges exists that transforms A into B, that is, there is a sequence of edges in G(R, S) that connects A and B. Thus the interchange graph G(R, S) is a connected graph.