Class of hypergraphs that are always the neighborhood hypergraph of some simple graph

Question

Let $G=(V,E)$ be a 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$.

It seems that not every hypergraph is the (open) neighborhood hypergraph of some graph. Indeed, it is NP-complete to decide if a given hypergraph is the (open) neighborhood hypergraph of some graph.

This makes me wonder: what kind of hypergraphs are always the (open) neighborhood hypergraphs of some graph? It would be particularly interesting to know the weakest possible structural requirements imposed on the class of hypergraphs such that each hypergraph belonging to the class is still a neighborhood hypergraph of some simple graph. Are there some examples at least?

Answer 1

Here is another way of thinking about the problem. Suppose for simplicity that your hypergraph $\mathcal{H}$ has exactly $|V(\mathcal{H})|$ hyperedges (as was mentioned by Dominic, we can immediately exclude any hypergraph with more hyperedges).

Let $G'$ be a bipartite graph where both parts are of size $|V(\mathcal{H})|$. We associate the left side of $G'$ with the vertices of $\mathcal{H}$ and, for each edge of $\mathcal{H}$, we make a vertex on the right side whose neighbourhood into the left side is exactly that hyperedge.

Now, if there is an automorphism $\phi$ of $G'$ such that $\phi^2$ is the identity, the vertices on the right are mapped to those on the left, and no vertex is mapped to a neighbour of itself, then identifying each vertex $v$ on the left with its image $\phi(v)$ gives you the desired graph $G$. In fact, when $\mathcal{H}$ has exactly $|V(\mathcal{H})|$ hyperedges, this is an "if and only if."

Thinking of if this way leads to some obvious conditions. For example, the degree sequence of the right side must be the same as the left side, etc.

If $\mathcal{H}$ has fewer than $|V(\mathcal{H})|$ hyperedges, then one can still construct $G'$, but will have to duplicate some vertices on the right side before trying to find the isomorphism. This seems to make things more complicated.

This brings up another question. You mention that the decision problem is NP-complete in general. However, is it possible that the problem becomes tractable for hypergraphs $\mathcal{H}$ with exactly $|V(\mathcal{H})|$ hyperedges? This seems to be related to the Graph Isomorphism Problem, but perhaps easier. If it is tractable for this class, then the difficulty in general must come down to finding the right way of duplicating vertices on the right side of $G'$.

By the way, this type of problem can have some very nice applications. For example, there is a paper of Labeznik, Ustimenko and Woldar (1999) where they obtain a new lower bound on the Turán number of the $6$-cycle by showing that a special class of hypergraphs, known as "generalised polygons," can be represented by the neighbourhood hypergraph of a graph (perhaps with loops). Their approach is pretty much exactly what I described above, but is presented in different language.

Answer 2

A partial answer is that a necessary but probably not sufficient condition for ${\cal H}$ is that it needs to have at most $|V|$ hyperedges -- otherwise there can be no edge set $E$ on $V$ such that $\cal H$ is the set of open nbhoods of $G=(V,E)$.

An example of a hypergraph not representable by open nbhoods: Let $V$ be the set $\{1,2,3,4\}$ and ${\cal E}=\{V\setminus\{a,b\}: a<b\in V\}$ and set ${\cal H}=(V,{\cal E})$.

Answer 3

Another easy criterion is the following: If ${\cal H} = (V, {\cal E})$ is a hypergraph such that $\bigcap {\cal E} \neq \emptyset$, then there can not be a graph edge set $E$ on $V$ such that ${\cal H}$ is the set of open neighborhoods of $G=(V,E)$.

The simple reason is that if we are given any simple undirected graph $G=(V,E)$ on $V$, for every $v\in V$ the open neighborhood of $v$ does not contain $v$ - so the intersection of the edge set of the associated open neighborhood hypergraph is empty.