1
$\begingroup$

Given a hypergraph $H=(V,E)$ we associate to it its line graph $L(H)$ given by $V(L(H)) =E$ and $$E(L(H)) = \big\{\{e_1,e_2\}: e_1\neq e_2 \in E \text{ and } e_1\cap e_2 \neq \emptyset \big\}.$$

We say that a $H=(V,E)$ is a dense linear hypergraph if

  1. $V \notin E$,
  2. $\bigcup E = V$,
  3. whenever $e_1\neq e_2 \in E$ then $|e_1\cap e_2| \leq 1$, and
  4. given $a\neq b\in V$ there is $e\in E$ with $\{a,b\}\in e$.

Question. Given a simple, undirected graph $G$, is there a dense linear hypergraph $H$ such that $G$ is isomorphic to an induced subgraph of $L(H)$?

$\endgroup$

1 Answer 1

2
$\begingroup$

Choose an orientation of $G$. We will write $\vec{vw}\in E(G)$ for the edge with the orientation from $v$ to $w$. For every vertex $v\in V(G)$, define

$$\mathcal V(v):=\{v\}\;\cup\;\{(v,e)\mid e=\vec{wv}\in E(G)\}.$$

Let $H=(V,E)$ be the hypergraph with vertex set

$$V=\{v_0\}\;\cup\;\bigcup_{\llap{v\,\in\, }\rlap{V(G)}} \mathcal V(v).$$

In words: $H$ contains a distinguished vertex $v_0$, and for each vertex $v\in V(G)$, it contains a copy of $v$, as well as a further copy for every incoming edge to $v$. Now, for every $v\in V(G)$, let $H$ contain the edge

$$e_v:=\mathcal V(v)\;\cup\;\{(w,e)\mid e=\vec{vw}\in E(G)\}.$$

And also add an edge $\{v_0\}$. $H$ then satsifies conditions 1 - 3, and you can add additional edges to $H$ to make it satisfy 4 as well. The (induced) embedding of $G$ into $L(H)$ is obviously via $v\mapsto e_v$.

The distinguished vertex $v_0$ is there to make the construction satisfy condition 1 in the case thas $G$ consists of a single vertex. The extra $v$ in $\mathcal V(v)$ exists, so that vertices without incoming edges are correctly represented.

$\endgroup$

You must log in to answer this question.

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