Intersection multigraphs of uniform hypergraphs
type: Item
instance of: scholarly article
title: Intersection multigraphs of uniform hypergraphs
zbMATH Open document ID: 0910.05048
published in: Graphs and Combinatorics
publication date: 1999-04-09T00:00:00Z
review text: 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.
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1234340
zbMATH Keywords: intersection multigraphs
zbMATH Keywords: uniform hypergraphs
zbMATH Keywords: cliques
zbMATH Keywords: recognition algorithm
author: Erich Prisner
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1234340