# 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

PDF

**Minisymposium:**
GRAPH DOMINATION

**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.