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$ Commented 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$ Commented Sep 22, 2015 at 7:43
  • $\begingroup$ Sorry, it appears that the answer does not depend on it ;)... $\endgroup$ Commented 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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .