Universitat Politècnica de Catalunya
Universitat Politècnica de Catalunya. Departament de Matemàtiques
Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions
Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta
2015-11
The collection of the vertex dominating sets of a graph defines a hypergraph on the set of vertices of the graph. However, there are hypergraphs H that are not the collection of the vertex dominating sets of any graph. This paper deals with the question of completing these hypergraphs H to the vertex dominating sets of some graphs G. We demonstrate that such graphs G exist and, in addition, we prove that these graphs define a poset whose minimal elements provide a decomposition of H. Moreover, we show that the hypergraph H is uniquely determined by the minimal elements of this poset. The computation of such minimal elements is also discussed in some cases.
Peer Reviewed
Postprint (author's final draft)
Article
English
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs; Graph theory; Graph; hypergraph; dominating set; Grafs, Teoria de; Classificació AMS::05 Combinatorics::05C Graph theory
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Open Access
E-prints [72986]
