ABSTRACT
A subset of vertices of a graph is a dominating set if every vertex is in the set or is adjacent to one of the vertices of the set. A dominating set is said to be paired if its induced subgraph contains a perfect matching. The domination and paired domination problems are to compute a dominating set and a paired dominating set, respectively, of a graph with minimum cardinality. Domination and its variants have applications in many fields, including network center allocation, very-large-scale integration (VLSI) layout, guard location systems, and more. In the past, we have proposed a generalization of hypergrid graphs called extended hypergrid graphs, including grid graphs, triangular grid graphs, and hypergrid graphs as their subclasses. The domination and independent domination problems for hypergrid and grid graphs were known to be NP-complete. However, the complexity of the paired domination problem for these two graph classes remains unknown. In this paper, we will prove that the paired domination problem on hypergrid graphs is NP-complete
