Abstract
dc:description.abstractA 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.
Degree
thesis:*- Name thesis:degree_name
- MS (Master of Science)
- Level thesis:degree_level
- Thesis - unrestricted
- Discipline thesis:degree_discipline
- Mathematical Sciences
- Year dc:date.issued
- 2014
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Rodriguez, Tony K
Subjects
dc:subject × 4Rights
dc:rights- Statement dc:rights
-
- Copyright by the authors.
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://dc.etsu.edu/etd/2345