Degree Name
MS (Master of Science)
Program
Mathematical Sciences
Date of Award
5-2014
Committee Chair or Co-Chairs
Teresa Haynes
Committee Members
Robert A. Beeler, Robert Gardner
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, and the minimum cardinality of a dominating set of G is the domination number of G. A vertex v in a dominating set S is said to be very cost effective if it is adjacent to more vertices in V\S than to vertices in S. A dominating set S is very cost effective if every vertex in S is very cost effective. The minimum cardinality of a very cost effective dominating set of G is the very cost effective domination number of G. We first give necessary conditions for a graph to have equal domination and very cost effective domination numbers. Then we determine an upper bound on the very cost effective domination number for trees in terms of their domination number, and characterize the trees which attain this bound. lastly, we show that no such bound exists for graphs in general, even when restricted to bipartite graphs.
Document Type
Thesis - unrestricted
Recommended Citation
Rodriguez, Tony K., "Very Cost Effective Domination in Graphs" (2014). Electronic Theses and Dissertations. Paper 2345. https://dc.etsu.edu/etd/2345
Copyright
Copyright by the authors.