Name of operation over bipartite graph

131 Views Asked by At

Given a bipartite graph $G_0=(V_1\cup V_2, E_0),$ I want to build another graph $G_1=(V_1,E_1)$, where its edges are defined from the part $V_2$, in this way: $$ E_1=\{(v_1,v_2): v_1,v_2\in V_1 \text{ and they share a neighbor}\}$$

A picture for reference, notice the colors of the edges.

enter image description here

This can be seen as a projection over the incidence matrix, also one can do the same operation but on the other part of $G$, i want to know what properties the resulting graphs, $G_1$ and $G_2$, have.

I don't think I'm the first person to think of this so I hope to find some background, reference material or keywords. Thanks!

2

There are 2 best solutions below

0
On BEST ANSWER

This is known as a bipartite half or half-square of a graph.

(In general, one notion of the square $G^2$ of a graph $G$ is the graph on the same vertex set with an edge whenever two vertices are at most distance $2$ apart in $G$; if we take the square of a bipartite graph, and then take the subgraph induced by one part, we get the half-square.)

It is also not uncommon to go from a bipartite graph to the hypergraph with vertex set $V_1$ where, for every vertex in $V_2$, we add a hyperedge through all of its neighbors.

0
On

In graph theory, this operation is also called a projection. Wikipedia has an article on bipartite network projection, but it generalizes to multipartite networks.