MS (Master of Science)
Date of Award
Committee Chair or Co-Chairs
Robert A. Beeler, Robert Gardner
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.
Thesis - Open Access
Rodriguez, Tony K., "Very Cost Effective Domination in Graphs" (2014). Electronic Theses and Dissertations. Paper 2345. http://dc.etsu.edu/etd/2345
Copyright by the authors.