Computational geometry seminar: Mercè Mora

COMPUTATIONAL GEOMETRY SEMINAR 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) Title: Graphs, hypergraphs and dominating sets Speaker: Mercè Mora Universitat Politècnica de Catalunya

  • Computational geometry seminar: Mercè Mora
  • 2016-04-28T13:15:00+02:00
  • 2016-04-28T14:15:00+02:00
  • COMPUTATIONAL GEOMETRY SEMINAR 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) Title: Graphs, hypergraphs and dominating sets Speaker: Mercè Mora Universitat Politècnica de Catalunya
Quan?

28/04/2016 de 13:15 a 14:15 (Europe/Madrid / UTC200)

On?

Room S215 Omega Building, Campus Nord UPC (equiv.: Room 215 Floor -2)

Afegiu l'esdeveniment al calendari

iCal

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

Activities are regularly announced a
http://www-ma2.upc.edu/dccg/upc-seminar-on-computational-geometry/