Completion and decomposition of hypergraphs by domination hypergraphs

• Autores: José Luis Ruiz Muñoz
• Directores de la Tesis: Jaume Martí Farré (dir. tes.) , Mercé Mora Giné (codir. tes.)
• Lectura: En la Universitat Politècnica de Catalunya (UPC) ( España ) en 2017
• Idioma: español
• Tribunal Calificador de la Tesis: Miguel Ángel Fiol Mora (presid.) , Josep Maria Miret Biosca (secret.) , María Luz Puertas González (voc.)
• Enlaces
  • Tesis en acceso abierto en: TDX
• Resumen

  • A graph consists of a finite non-empty set of vertices and a set of unordered pairs of vertices, called edges. A dominating set of a graph is a set of vertices D such that every vertex not in D is adjacent to some vertex in D. A hypergraph on a finite set X is a collection of subsets of X, none of which is a proper subset of another. The domination hypergraph of a graph is the collection of all the minimal vertex dominating sets of the graph. A hypergraph is a domination hypergraph if it is the domination hypergraph of a graph. In general, a hypergraph is not a domination hypergraph. The objective of this work is to approximate a hypergraph by domination hypergraphs and that the optimal approximations determine uniquely the hypergraph.

    In Chapter 1 we introduce two structures of distributive lattices on the set of hypergraphs on a finite set and also define some operations: the complementary hypergraph and two transversal operations. We study the behavior of these operations with respect to the partial orders and the lattice structures.

    In Chapter 2 we first introduce several hypergraphs associated with a graph, the most important one being the domination hypergraph, and we establish several relationships among them. Then we compute the domination hypergraph of all graphs, modulo isomorphism, up to order 5. We also investigate when a given hypergraph is a domination hypergraph and find all domination hypergraphs in some cases.

    In Chapter 3 we present the problem of approximating a hypergraph by domination hypergraphs. We introduce four families of approximations of a hypergraph, which we call completions, depending on which partial order we use and on which side we approximate. We set some sufficient conditions for the existence of completions, introduce the sets of minimal or maximal completions of a hypergraph and study the concept of decomposition, which leads to the decomposition index of a hypergraph. Avoidance properties turn out to be an essential ingredient for the existence of domination completions.

    In Chapter 4 we give some computational techniques and calculate the upper minimal domination completions and the decomposition indices of some hypergraphs.

    In the appendices we give the SAGE code developed to perform the calculations of the thesis and we list all the domination hypergraphs of all graphs of order 5 and all the graphs of order 5 with the same domination hypergraph.