1
$\begingroup$

I am working on a combinatorial optimization problem and have constructed a bipartite graph as a representation of a directed graph.

The construction is as follows:

Given an initial directed graph $G$ with $N$ nodes, I form a new directed bipartite graph $G_B$. In the left partition of $G_B$, there are $N$ nodes labeled $n_{i,\text{from}}$, and in the right partition, there are $N$ nodes labeled $n_{j,\text{to}}$. Thus, $G_B$ has a total of $2N$ nodes. For each edge $(n_i, n_j)$ in the original graph $G$, I add a corresponding edge $(n_{i,\text{from}}, n_{j,\text{to}})$ in $G_B$.

See Figure 1 from a paper by Miguel A. Méndez (https://doi.org/10.1007/s00026-001-8022-8) which matches this construction I am looking for. (Here is a static link to the figure: https://i.sstatic.net/VeqoAdth.png)

I found two other papers (Figure 6 in https://arxiv.org/abs/2208.10959 and Figure 1 in https://doi.org/10.1002/2017WR020861) referring to or related to this type of construction, but it appears only as a small and minor part of the overall work. In these instances, the origin of construction is neither discussed in depth nor referenced through related literature.

I have attempted to find references or established terminology for this “bipartite representation of a directed graph” but have not yet discovered a standard name or related literature.

Does anyone know if this construction has a known name, or if there is any literature focusing on this type of construction?

Improve this question
$\endgroup$
1
  • $\begingroup$ It's a tensor product of G with $\vec{P_2}$, or the bipartite graph you obtain by interpreting the adjacency matrix of G as a biadjacency matrix. I'm not aware of any established name for it, though it does pop up in different settings. See: mathoverflow.net/questions/234862/… $\endgroup$
    – Marcin Wrochna
    Commented Dec 9 at 15:54

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .