Intersection multigraphs of uniform hypergraphs (Q1272535)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Intersection multigraphs of uniform hypergraphs |
scientific article |
Statements
Intersection multigraphs of uniform hypergraphs (English)
0 references
9 April 1999
0 references
A hypergraph \(H=(V,\{X_i \mid i\in I\})\) is \(k\)-uniform if all hyperedges \(X_i\) have the same cardinality \(k\); it is \(k\)-conformal if there is some graph \(G\) such that \(H\) is isomorphic to the hypergraph of all cliques with \(k\) vertices of \(G\). The intersection multigraph of \(H\) has \(\{x_i \mid i\in I\}\) as vertex set, and two distinct vertices \(x_i\), \(x_j\) are joined by \(| X_i\cap X_j| \) parallel edges. While the recognition problem of intersection multigraphs of \(k\)--uniform hypergraphs \((k\geq 3)\) is NP-complete, the author shows that intersection multigraphs of 3-uniform, 3-conformal hypergraphs can be recognized and the (essentially unique) root hypergraph can be reconstructed in polynomial time. Intersection multigraphs of \(k\)-uniform, \(k\)-conformal hypergraphs \((k\geq 4)\) with one additional property are also discussed.
0 references
intersection multigraphs
0 references
uniform hypergraphs
0 references
cliques
0 references
recognition algorithm
0 references