Title: The Domination and Independent Domination Problems in Supergrid Graphs
Abstract: Let G be a graph with vertex set V(G) and edge set E(G). A subset D of V(G) is a dominating set of G if every vertex not in D is adjacent to one vertex of D. A dominating set is called independent if it is an independent set. The domination number (resp., independent domination number) of G, denoted by \(\gamma (G)\) (resp., \(\gamma _{\mathrm {ind}}(G)\)), is the minimum cardinality of a dominating set (resp., independent dominating set) of G. The domination (resp., independent domination) problem is to compute a dominating set (resp., an independent dominating set) of G with size \(\gamma (G)\) (resp., \(\gamma _{\mathrm {ind}}(G)\)). Supergrid graphs are a natural extension for grid graphs. The domination and independent domination problems for grid graphs were known to be NP-complete. However, their complexities on supergrid graphs are still unknown. In this paper, we will prove these two problems for supergrid graphs to be NP-complete. Then, we compute \(\gamma (R_{m\times n})\) and \(\gamma _{\mathrm {ind}}(R_{m\times n})\) for rectangular supergrid graphs \(R_{m\times n}\) in linear time.
Publication Year: 2021
Publication Date: 2021-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 3
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot