Degree Name
MS (Master of Science)
Program
Mathematical Sciences
Date of Award
12-2012
Committee Chair or Co-Chairs
Teresa W. Haynes
Committee Members
Debra J. Knisley, Robert A. Beeler
Abstract
A set S of vertices in a graph G = (V,E) is a dominating set if every vertex in V \ S is adjacent to at least one vertex in S. A vertex v in a dominating set S is said to be it cost effective if it is adjacent to at least as many vertices in V \ S as it is in S. A dominating set S is cost effective if every vertex in S is cost effective. The minimum cardinality of a cost effective dominating set of G is the cost effective domination number of G. In addition to some preliminary results for general graphs, we give lower and upper bounds on the cost effective domination number of trees in terms of their domination number and characterize the trees that achieve the upper bound. We show that every value of the cost effective domination number between these bounds is realizable.
Document Type
Thesis - unrestricted
Recommended Citation
McCoy, Tabitha Lynn, "Cost Effective Domination in Graphs" (2012). Electronic Theses and Dissertations. Paper 1485. https://dc.etsu.edu/etd/1485
Copyright
Copyright by the authors.