Off-campus ETSU users: To download "Campus Only" theses, please use the following link to log in to our proxy server with your ETSU username and password.

Non-ETSU users: Please talk to your librarian about requesting this thesis through interlibrary loan.

Degree Name

MS (Master of Science)

Program

Mathematical Sciences

Date of Award

5-2001

Committee Chair or Co-Chairs

Teresa W. Haynes

Committee Members

Debra J. Knisley, Janice Huang

Abstract

Every graph G = (V, E) has a dominating set SV(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.

Document Type

Thesis - Campus Only

Copyright

Copyright by the authors.

Share

COinS