rjtobin, Sorry I don't understand what happens if the two graphs have common vertices?
For example, in the algebra I described, you can do 1 -> (1 + 2) and this represents a graph with vertices {1,2} and two edges (1,1) and (1,2). How would that work with your matrix join?
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.
For example, in the algebra I described, you can do 1 -> (1 + 2) and this represents a graph with vertices {1,2} and two edges (1,1) and (1,2). How would that work with your matrix join?