Abstract
dc:description.abstract<p>Every graph <em>G</em> = (<em>V</em>, <em>E</em>) has a dominating set <em>S</em> ⊆ <em>V</em>(<em>G</em>) such that any vertex not in <em>S</em> is adjacent to a vertex in <em>S</em>. We define a paired-dominating set <em>S</em> to be a dominating set <em>S</em> = {<em>v</em><sub>1</sub>, <em>v</em><sub>2</sub>,..., <em>v</em><sub>2<em>t</em>-1</sub>, <em>v</em><sub>2<em>t</em></sub>} where <em>M</em> = {<em>v</em><sub>1</sub><em>v</em><sub>2</sub>, <em>v</em><sub>3</sub><em>v</em><sub>4</sub>, ..., <em>v</em><sub>2<em>t</em>-1</sub><em>v</em><sub>2<em>t</em></sub>} is a perfect matching in 〈<em>S</em>〉, the subgraph induced by <em>S</em>. The domination number of a graph <em>G</em> is the smallest cardinality of any dominating set of <em>G</em>, 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 <em>G<sub>r</sub></em>,<em>c</em> where <em>r</em> ∈ {2,3}, for infinite dimensional grid graphs, and for the complement of a grid graph.</p>
Degree
thesis:*- Name thesis:degree_name
- MS (Master of Science)
- Level thesis:degree_level
- Thesis - restricted
- Discipline thesis:degree_discipline
- Mathematical Sciences
- Year dc:date.issued
- 2001
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Proffitt, Kenneth Eugene
Subjects
dc:subject × 4Rights
dc:rights- Statement dc:rights
-
- Copyright by the authors.
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://dc.etsu.edu/etd/131
- OAI identifier oai:identifier
- oai:dc.etsu.edu:etd-1181