TOPICS
Search

(0,1)-Matrix Interchange Graph

The (0,1)-matrix interchange graph G(R,S) for vectors R and S is the graph whose vertex set is A(R,S), where A(R,S) is the class of (0,1)-matrices with row sum vector R and column sum vector S, and in which two matrices in A(R,S) are adjacent exactly when one is obtained from the other by a single 2×2 interchange, i.e., by complementing all four entries of a checkerboard 2×2 submatrix (Baggett and Yan 2026). This use of the term interchange graph is distinct from its older use as a synonym for a line graph (van Rooij and Wilf 1965).

When R=S=(1,...,1), the vertices are permutation matrices and G(R,S) is the complete transposition graph. Baggett and Yan (2026) proved that G(R,S) is H*-connected whenever A(R,S) is nonempty.

See also

(0,1)-Matrix, H*-Connected Graph, Line Graph, Transposition Graph

Explore with Wolfram|Alpha

References

Baggett, J. S. and Yan, H. "Interchange Graphs of (0,1)-Matrices Are Maximally Hamiltonian." 14 Jul 2026. https://arxiv.org/abs/2607.13165.van Rooij, A. C. M. and Wilf, H. S. "The Interchange Graph of a Finite Graph." Acta Math. Acad. Sci. Hungar. 16, 263-269, 1965. https://doi.org/10.1007/BF01904834.

Cite this as:

Weisstein, Eric W. "(0,1)-Matrix Interchange Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/01-MatrixInterchangeGraph.html

Subject classifications