What are the analogous matrix operations of graph union and intersection operations?

Question

I know that a graph can be represented by its adjacency matrix. Graph union and graph intersection are two important basic operations in graph theory. Working with graphs and their operations is good to visualise certain relations or social networking etc., but when it comes to computational (programming) part, it becomes difficult to feed the graphs directly into our systems (computers). Hence it often requires to be converted into corresponding matrix form. Suppose, in case i am coverting the matrices into corresponding adjacency matrices,

What are possible analogous matrix operations of graph union and graph intersection operations?

Note that the graph i am talking about is simple and undirected

Answer 1

These are not very natural operations from the point of view of linear algebra, but we can define them on matrices (and compute them in MATLAB or whatever).

• For the intersection of two graphs with adjacency matrices $A$ and $B$, we take the element-wise $\min$ of their entries: that is, the $(i,j)$-th entry of the result should be $$\min(A,B)_{ij} = \min(A_{ij}, B_{ij}).$$
• For the union of two graphs, we take the element-wise $\max$ of their entries.

For example, if I have the graphs

1 -- 2 -- 3               1 -- 3 -- 2

then their adjacency matrices are, respectively, $$ A = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0\end{bmatrix} \qquad B = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 0\end{bmatrix}. $$ The min and the max will be $$ \min(A,B) = \begin{bmatrix}0 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 0\end{bmatrix} \qquad \max(A,B) = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix} $$ and these are the intersection and the union of the two graphs.