{"id":"arxiv/2607.13165","url":"https://arxiv.org/abs/2607.13165","tags":["math.CO","cs.DM"],"score":0,"title":"Interchange graphs of (0,1)-matrices are maximally Hamiltonian","domain":"math.CO","source":"arxiv","authors":["Jeffrey S. Baggett","Huiya Yan"],"reviews":0,"subject":"math.CO","summary":"For integer vectors R,S let A(R,S) denote the class of (0,1)-matrices with row sum vector R and column sum vector S. Its interchange graph G(R,S) has A(R,S) as its vertex set, two matrices being adjacent when they differ by a single 2 x 2 interchange. Brualdi asked whether G(R,S) is Hamiltonian for every R,S. We prove the stronger statement that G(R,S) is maximally Hamiltonian: Hamilton-laceable when bipartite, and Hamilton-connected when not. The proof is a structural induction on the number of matrices in the class, organized by the structure theory of interchange graphs. Deleting inactive…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-14","reactions":{}}