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?
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – smapers Mar 25 at 17:25
  • 2
    $\begingroup$ 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$. $\endgroup$ – Neal Young Mar 31 at 15:37

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.