1
$\begingroup$

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!

Improve this question
$\endgroup$
8
  • 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
    Commented Mar 31, 2016 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
    Commented Mar 31, 2016 at 11:42
  • $\begingroup$ Thank you! Could you please refer to literature where such things come up? @JonNoel $\endgroup$
    – root
    Commented Apr 2, 2016 at 11:22
  • $\begingroup$ Could you please refer to literature where this common observation appears? @BrendanMcKay $\endgroup$
    – root
    Commented Apr 2, 2016 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
    Commented Feb 26, 2018 at 8:52

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .