Uniform hypergraphs and vertex dominating sets of graphs

Merc\`e Mora
Universitat Polit\`ecnica de Catalunya

Jaume Mart\'i-Farr\'e
Universitat Polit\`ecnica de Catalunya

Jos\'e Luis Ruiz
Universitat Polit\`ecnica de Catalunya



Content: The collection of the minimal dominating sets of a graph is a hypergraph. However, there are hypergraphs $H$ that are not the collection of the vertex dominating sets of any graph. We say that a hypergraph $H$ is a \emph{domination hypergraph} if there is at least a graph $G$ such that the collection of minimal dominating sets of $G$ is equal to $H$. Given a hypergraph, we are interested in determining if it is a domination hypergraph, otherwise we want to find domination hypergraphs ``close'' to it. To solve this problem, we define the \emph{domination completions} of a hypergraph. Moreover, we prove that it is possible to recover a hypergraph from suitable domination completions. Here we will focus on the case of uniform hypergraphs, that is, hypergraphs whose elements are all the subsets with the same cardinality. Concretely, we characterize all the uniform hypergraphs that are domination hypergraphs and, in some other cases, we give those domination completions that allow us to recover the hypergraph.

Back to all abstracts