Roman domination in subgraphs of grids

详细信息    查看全文

• 作者：Samuel Nascimento¹ ; ^{samuel.nascimento@lia.ufc.br" class="auth_mail" title="E-mail the corresponding author} ; Rudini Sampaio¹ ; ^{rudini@lia.ufc.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Roman domination ; APX-hard ; Fixed parameter tractable ; grid
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：50
• 期：Complete
• 页码：77-82
• 全文大小：226 K

文摘

In a Roman domination of a graph, vertices are assigned a value from {0,1,2}$\{0,1,2\}$ in such a way that every vertex assigned the value 0 is adjacent to a vertex assigned the value 2. The Roman domination number is the minimum possible sum of all values in such an assignment. In this paper, we prove that the Roman domination number is NP-hard even for subgraphs of grids and it is APX-hard even for bipartite graphs with maximum degree 4. We also prove that the Roman domination number is fixed parameter tractable for graphs with bounded local treewidth, as graphs with bounded maximum degree or bounded genus (like planar graphs or toroidal graphs). We also obtain complexity results regarding the number of Roman dominating sets.