Let the adjacency matrix of an undirected bipartite graph be $A = \begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix}$ where B is called the biadjacency matrix.

Now, by instead interpreting B as an adjacency matrix of a not necessarily bipartite (arbitrary) directed graph, we get a bijection between the bipartite undirected graph (with biadjacency matrix B) and the arbitrary directed graph (with adjacency matrix B).

Does this bijection have a name? Is it discussed somewhere in literature? Thank you!

  • 1
    $\begingroup$ This sort of thing comes up often, but I don't know if it has a name. One observation is that the bipartite graph is obtained by taking the direct product (categorical product) of the digraph with K_2. $\endgroup$ – Jon Noel Mar 31 '16 at 11:37
  • 4
    $\begingroup$ Note that it only makes sense if $B$ is square, which eliminates most bipartite graphs. As Jon writes, it is a common observation but I don't recall a specific name for it. $\endgroup$ – Brendan McKay Mar 31 '16 at 11:42
  • $\begingroup$ Thank you! Could you please refer to literature where such things come up? @JonNoel $\endgroup$ – root Apr 2 '16 at 11:22
  • $\begingroup$ Could you please refer to literature where this common observation appears? @BrendanMcKay $\endgroup$ – root Apr 2 '16 at 11:22
  • $\begingroup$ @root: I take issue with the term "equivalence relation" in this OP. I think what you mean is simply 'we get a map $\textsf{UndirectedBipartiteGraphs}$ $\to$ $\textsf{DirectedGraphs}$. I don't see how 'equivalence relation' makes any sense here. On what set should this relation be defined? How should it even be reflexive? Would you please clarify and possibly edit the question accordingly? Also, saying "non-bipartite" is wrong: this directed graph can happen to be bipartite. The correct way to put is "a not necessarily bipartite directed graph". $\endgroup$ – Peter Heinig Feb 26 '18 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.