0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Do you consider a hypergraph or a multi-hypergraph? It seems that the answer for the second question depends on it. $\endgroup$ Sep 22, 2015 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$ Sep 22, 2015 at 7:43
  • $\begingroup$ Sorry, it appears that the answer does not depend on it ;)... $\endgroup$ Sep 22, 2015 at 7:57

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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