Article in volume
Authors:
Title:
Edge intersection hypergraphs
PDFSource:
Discussiones Mathematicae Graph Theory 44(1) (2024) 101-126
Received: 2021-04-28 , Revised: 2021-10-07 , Accepted: 2021-10-07 , Available online: 2021-10-22 , https://doi.org/10.7151/dmgt.2435
Abstract:
If ${\cal H}=(V,{\cal E})$ is a hypergraph, its edge intersection hypergraph
$EI({\cal H})=(V,{\cal E}^{EI})$ has the edge set ${\cal E}^{EI}=\{e_1 \cap e_2 \ |\ e_1, e_2 \in
{\cal E} \ \wedge \ e_1 \neq e_2 \ \wedge \ |e_1 \cap e_2 |\geq2\}$. 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.
Using the so-called clique-fusion, as a conclusion we obtain that nearly
all cacti are edge intersection hypergraphs of 3-uniform hypergraphs, too.
Keywords:
edge intersection hypergraph, tree, cactus
References:
- C. Berge, Graphs and Hypergraphs (North Holland, Amsterdam, 1973).
- T. Biedl and M. Stern, On edge-intersection graphs of $k$-bend paths in grids, Discrete Math. Theor. Comput. Sci. 12 (2010) 1–12.
https://doi.org/10.46298/dmtcs.482 - K. Cameron, S. Chaplick and C.T. Hoang, Edge intersection graphs of $L$-shaped paths in grids, Discrete Appl. Math. 210 (2016) 185–194.
https://doi.org/10.1016/j.dam.2015.01.039 - M.C. Golumbic and R.E. Jamison, The edge intersection graphs of paths in a tree, J. Combin. Theory Ser. B 38 (1985) 8–22.
https://doi.org/10.1016/0095-8956(85)90088-7 - R.N. Naik, S.B. Rao, S.S. Shrikhande and N.M. Singhi, Intersection graphs of $k$-uniform linear hypergraphs, European J. Combin. 3 (1982) 159–172.
https://doi.org/10.1016/S0195-6698(82)80029-2 - R.C. Read and R.J. Wilson, An Atlas of Graphs (Oxford University Press, New York, 1998).
- G. Robers, EI-Hypergraphen und deren Eigenschaften, Bachelor Thesis (University of Lübeck, 2017).
- P.V. Skums, S.V. Suzdal and R.I. Tyshkevich, Edge intersection graphs of linear $3$-uniform hypergraphs, Discrete Math. 309 (2009) 3500–3517.
https://doi.org/10.1016/j.disc.2007.12.082 - M. Sonntag and H.-M. Teichert, Cycles as edge intersection hypergraphs, (2019).
arXiv: 1902.00396 - Wolfram Research, Inc., Mathematica (2010), Version 8.0, Champaign, IL.
Close