Edge intersection hypergraphs - a new hypergraph concept

Abstract

If $\mathcal{H}=(V,\mathcal{E})$ is a hypergraph, its edge intersection hypergraph $EI(\mathcal{H})=(V,{\mathcal{E}}^{EI})$ has the edge set ${\mathcal{E}}^{EI}=\{e_1\cap e_2|e_1,e_2\in \mathcal{E}\wedge e_1\ne e_2\wedge |e_1\cap e_2|\ge 2\}$. Besides investigating several structural properties of edge intersection hypergraphs, we prove that all trees but seven exceptional ones are edge intersection hypergraphs of 3-uniform hypergraphs.

15 pages, 3 figures

Cited by in corpus (2)

• Nearly all cacti are edge intersection hypergraphs of 3-uniform hypergraphs
• Cycles as edge intersection hypergraphs