Back to search

East Tennessee State University

Paired-Domination in Grid Graphs.

Abstract

dc:description.abstract

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, v2,..., v2t-1, v2t} where M = {v1v2, v3v4, ..., v2t-1v2t} 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.

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 × 4

Rights

dc:rights
Statement dc:rights
  • Copyright by the authors.

Identifiers

dc:identifier.*
Repository record dc:identifier
https://dc.etsu.edu/etd/131

Chain of custody

source
Harvested from
East Tennessee State University
Base URL
dc.etsu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Proffitt, Kenneth Eugene. Paired-Domination in Grid Graphs.. Thesis - restricted thesis, 2001. https://dc.etsu.edu/etd/131