| Every graph G = (V, E) has a dominating set S ⊆ V(G) such that any vertex not, in S is adjacent to a vertex in S. We define a paired-dominating set S to be a dominating set S = {v1, v 2,…, v2t −1,v2t} with independent edge set M = {v1 v2,v3v 4,…, v2t −1, v2t} that is a perfect matching in ⟨S⟩, the subgraph induced by S. The domination number of a graph G is the smallest cardinality of any dominating set of G, and the paired-domination number is the smallest cardinality of any paired-dominating set. Determining the domination number for grid graphs is a well-known open problem in graph theory. Not surprisingly, determining the paired-domination number for grid graphs is also a difficult problem. In this thesis, we survey past research in domination, paired-domination and grid graphs to obtain background for our study of paired-domination in grid graphs. We determine the paired-domination number for grid graphs Gr,c where r ∈ {2, 3}, for infinite dimensional grid graphs, and for the complement of a grid graph. |
