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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.