I didn't really think about that case. In full generality, then the corresponding (n+m-k)x(n+m-k) matrix can be written as the matrix whose top-left (n-k)x(n-k) block is A\B, whose bottom-right (m-k)x(m-k) block is B\A, and where everything else is 1.

Note that both involve relabelling vertices. Many graph theorists do this freely (it's the same graph), but perhaps you have some application in mind where you don't want to do this.