Completion and decomposition of hypergraphs into dominating sets of graphs

详细信息    查看全文

• 作者：Jaume Martí ; -Farré ; ^a ; ¹ ; ^{jaume.marti@ma4.upc.edu" class="auth_mail" title="E-mail the corresponding author} ; Mercè ; Mora^b ; ² ; ^{merce.mora@upc.edu" class="auth_mail" title="E-mail the corresponding author} ; José ; Luis Ruiz^b ; ^{jose.luis.ruiz@upc.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Graph ; hypergraph ; dominating set
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2015
• 出版时间：November 2015
• 年：2015
• 卷：49
• 期：Complete
• 页码：213-220
• 全文大小：183 K

文摘

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.