Computational geometry seminar 28-04-2016

Title: Graphs, hypergraphs and dominating sets
Speaker: MERCÈ MORA

Thursday, April 28, 2016, 13:15-14:15 (15 minutes delayed with respect to the usual schedule)
Room S215 Omega Building, Campus Nord UPC (equiv.: Room 215 Floor -2) 

Abstract: A 'simple hypergraph' is a collection of non-comparable subsets of a set of vertices. The elements of the hypergraph are called 'hyperedges'. A graph can be viewed as a hypergraph with hyperedges of size 2.

Many concepts of graphs give rise to a collection of subsets of vertices that allows us to consider hypergraphs associated with the graph by considering the collection of minimal or maximal elements. Namely, we will handle with the collection of closed neighborhoods, dominating sets, vertex covering sets and independent sets. We study the relationships between them by using some hypergraph operations.

Finally, we focus on the case of dominating sets. A hypergraph is a 'domination hypergraph' if it is the collection of the minimal dominating sets of some graph. We are interested in determining when a hypergraph is a domination hypergraph and, if it is not the case, we seek domination hypergraphs close to it, the domination completions. Moreover, we prove that the hypergraph is univocally characterized by some domination completions, the 'minimal domination completions'.

We discuss in more detail the case of k-uniform complete 'hypergraphs', that is, hypergraphs containing all the k-subsets of a set of vertices. 

Joint work with Jaume Martí-Farré and José Luis Ruiz.