For any set $X$ we let $[X]^2 = \big\{\{x,y\}: x\neq y \in X\big\}$.

Let $G=(V,E)$ be a simple, undirected graph. Its open neighborhood hypergraph $\mathcal{H}(G)$ has the same vertex set $V$ with a hyperedge for the open neighborhood of every vertex $v \in V$. (The open neighborhood of $v\in V$ is the set $N_v = \{y\in V: \{x,y\}\in E\}$.)

Given a non-empty set $V$, are there $E_1\neq E_2\subseteq [V]^2$ such that ${\cal H}(V,E_1) = {\cal H}(V,E_2)$? Can $E_1, E_2$ even be chosen such that the graphs $(V,E_1), (V,E_2)$ are not isomorphic?

  • $\begingroup$ Do you consider a hypergraph or a multi-hypergraph? It seems that the answer for the second question depends on it. $\endgroup$ – Ilya Bogdanov Sep 22 '15 at 7:42
  • $\begingroup$ I was just thinking of hypergraphs $H=(V,E)$ where $V$ is a set and $E\subseteq {\cal P}(V)$ $\endgroup$ – Dominic van der Zypen Sep 22 '15 at 7:43
  • $\begingroup$ Sorry, it appears that the answer does not depend on it ;)... $\endgroup$ – Ilya Bogdanov Sep 22 '15 at 7:57

The answer to the first question is positive. Consider two graphs on eight vertices each consisting of two disjoint 4-cycles: the first one's cycles are $abcd$ and $efgh$, the second's ones are $afch$ and $ebgd$.

The answer for the second question is also positive, even if we consider $\mathcal H(G)$ to be a multi-hypergraph (thus taking neighborhoods with multiplicities). Take any connected non-bipartite graph $G$ and construct two graphs from it: first one is the disjoint union of two copies of $G$, another one is the tensor product of $G$ with an edge. Both have the same neighborhood multi-hypergraph, but one is not connected and another one is.

If you need, say, only connected graphs you may also obtain such by augmenting both graphs by a vertex connected to all vertices.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.