Paired-domination in grid graphs [electronic resource] /

by Proffitt, Kenneth Eugene.; State University., East Tennessee

Abstract (Summary)
Every graph G = (V, E) has a dominating set S [a subset of] 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 = %7Bv?, v?, ..., v?t??, v?t%7D where M = %7Bv?v?, v?v? ..., v?t??v?t%7D is a perfect matching in (S), the subgraph induced by S. The domination number of a graph G is the smallest cardinality of any paired-dominating set. Determining the domination number for grid graphs in 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 G[subscript]r, c where r [is equivalent to] %7B2,3%7D, for infinite dimensional grid graphs, and for the complement of a grid graph.
Bibliographical Information:


School:East Tennessee State University

School Location:USA - Tennessee

Source Type:Master's Thesis

Keywords:paired domination grid graphs


Date of Publication:

© 2009 All Rights Reserved.