<p>Define the <em>common neighborhood</em> of two vertices <span class="math-container">$u$</span> and <span class="math-container">$v$</span> of a simple undirected graph as the set <span class="math-container">$N(u,v)=N(u)\cap N(v)$</span>. For a simple bipartite graph <span class="math-container">$G=(U,V,E)$</span>, define the <em>pairwise-common neighborhoods set</em> as <span class="math-container">$\{N(u_1,u_2):u_1\not=u_2\in U∧N(u_1,u_2)≠∅\}$</span>.</p>
<ol>
<li>Is it possible to recover a bipartite <span class="math-container">$G$</span> if given only its pairwise-common neighborhoods set? Assume <span class="math-container">$G$</span> connected and degree greater or equal than 2 for all vertices.</li>
<li>Is there an efficient algorithm that constructs <em>some</em> bipartite graph with a given pairwise-common neighborhoods set, or halts if one does not exist?</li>
</ol>

CC BY-SA 4.0
2021-03-25T17:25:54.130Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/121282/discussion-between-smapers-and-delete000).
smapers
CC BY-SA 4.0
2021-03-31T15:37:50.040Z
As stated (with the set given as input, without multiplicities), the answer to question 1 is no.  Given just the pairwise-common neighborhood set, without multiplicities, you can't distinguish the complete bipartite graphs $K_{n, 2}$ from $K_{n', 2}$ for any integers $n, n'\ge 2$.
Neal Young
CC BY-SA 4.0
2024-12-10T02:54:55.543Z
The graph turnpike problem seems to be related. https://www.sciencedirect.com/science/article/abs/pii/S0020019009001021
delete000
<graph-theory><graph-algorithms>
Graph recovery from pairwise-common neighborhoods
delete000
# Graph recovery from pairwise-common neighborhoods

(Asked by: username_0 on 2021-03-24)

Define the *common neighborhood* of two vertices $u$ and $v$ of a simple undirected graph as the set $N(u,v)=N(u)\cap N(v)$. For a simple bipartite graph $G=(U,V,E)$, define the *pairwise-common neighborhoods set* as $\{N(u\_1,u\_2):u\_1\not=u\_2\in U∧N(u\_1,u\_2)≠∅\}$.

1. Is it possible to recover a bipartite $G$ if given only its pairwise-common neighborhoods set? Assume $G$ connected and degree greater or equal than 2 for all vertices.
2. Is there an efficient algorithm that constructs *some* bipartite graph with a given pairwise-common neighborhoods set, or halts if one does not exist?

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/121282/discussion-between-smapers-and-delete000).  
> **username_2**: As stated (with the set given as input, without multiplicities), the answer to question 1 is no.  Given just the pairwise-common neighborhood set, without multiplicities, you can't distinguish the complete bipartite graphs $K_{n, 2}$ from $K_{n', 2}$ for any integers $n, n'\ge 2$.  
> **username_0**: The graph turnpike problem seems to be related. https://www.sciencedirect.com/science/article/abs/pii/S0020019009001021  

---

## 0 answers

