#### 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 - Open Access

#### Recommended Citation

Rodriguez, Tony K., "Very Cost Effective Domination in Graphs" (2014). *Electronic Theses and Dissertations.* Paper 2345. http://dc.etsu.edu/etd/2345

#### Copyright

Copyright by the authors.