1
$\begingroup$

Here's two random $(0,1)$-matrices: $$ A= \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ \end{bmatrix} \qquad B= \begin{bmatrix} 1 & 1 \\ 0 & 1 \\ \end{bmatrix}. $$ They can be interpreted as biadjacency matrices: the graph $G[A]$ has vertices $\{r_1,r_2\} \cup \{c_1,c_2,c_3\}$ and undirected edges $r_i c_j$ if and only if $A[i,j]=1$, and likewise for $B$.

If we take a Kronecker product of $A$ and $B$, we obtain: $$ A \otimes B=\begin{bmatrix} \color{red} 1 & \color{red} 1 & 0 & 0 & 0 & 0\\ \color{red} 0 & \color{red} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & \color{blue} 1 & \color{blue} 1 & \color{green} 1 & \color{green} 1 \\ 0 & 0 & \color{blue} 0 & \color{blue} 1 & \color{green} 0 & \color{green} 1 \\ \end{bmatrix} $$ And thus we have a bipartite graph $G[A \otimes B]$ with biadjacency matrix $A \otimes B$.

While I feel like this would have been studied, I don't know what this graph is called. I didn't find it on Wikipedia's list: the vertex set is not $V(G[A]) \times V(G[B])$.

Question: The Kronecker product of two bipartite graphs' biadjacency matrices: what's it called?

$\endgroup$

1 Answer 1

3
$\begingroup$

For bipartite graphs $G[A]$ and $G[B]$, their tensor product $G[A] \times G[B]$ is the disjoint union of bipartite graphs $G[A \otimes B]$ and $G[A \otimes B^T]$. See, for example, p.56 of Hammack, Imrich, Klavžar - Handbook of Product Graphs.

One possible reason why this extensive book doesn't mention this "product" any further is that there's usually no reason to consider $G[A \otimes B]$ over/apart from $G[A \otimes B^T]$ or vice versa in an undirected setting. Were edges of $G[A]$ and $G[B]$ directed from one half to another, their tensor product would consist of $G[A \otimes B]$ (with directed edges) and a bunch of isolated vertices.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.