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.
","abstract_html":"<p>A set <em>S</em> of vertices in a graph <em>G</em> = (<em>V</em>,<em>E</em>) is a dominating set if every vertex in <em>V</em> \\ <em>S</em> is adjacent to at least one vertex in <em>S</em>. A vertex <em>v</em> in a dominating set <em>S</em> is said to be it <em>cost effective</em> if it is adjacent to at least as many vertices in <em>V</em> \\ <em>S</em> as it is in <em>S</em>. 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 <em>G</em> 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.</p>","abstract_has_math":false,"creators":["McCoy, Tabitha Lynn"],"institution":null,"degree_name":"MS (Master of Science)","degree_level":"Thesis - unrestricted","degree_discipline":"Mathematical Sciences","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012-12-15T08:00:00Z","date_published":"2012-12-15T08:00:00Z","updated_at":"2026-07-24T02:20:42Z","subjects":["cost effective domination number","cost effective domination","Discrete Mathematics and Combinatorics","Mathematics","Physical Sciences and Mathematics"],"languages":[],"rights":["Copyright by the authors."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://dc.etsu.edu/etd/1485","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["McCoy, Tabitha Lynn"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2012-12-15T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematical Sciences"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis - unrestricted"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS (Master of Science)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["cost effective domination number","cost effective domination","Discrete Mathematics and Combinatorics","Mathematics","Physical Sciences and Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["Copyright by the authors."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://dc.etsu.edu/context/etd/article/2678/viewcontent/McCoyT103112f.pdf","https://dc.etsu.edu/etd/1485"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.
"]},{"key":"dc:title","label":"Title","values":["Cost Effective Domination in Graphs"]}]}],"canonical_facts":{"dc:creator":["McCoy, Tabitha Lynn"],"dc:date.issued":["2012-12-15T08:00:00Z"],"dc:description.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.
"],"dc:identifier":["https://dc.etsu.edu/context/etd/article/2678/viewcontent/McCoyT103112f.pdf","https://dc.etsu.edu/etd/1485"],"dc:rights":["Copyright by the authors."],"dc:subject":["cost effective domination number","cost effective domination","Discrete Mathematics and Combinatorics","Mathematics","Physical Sciences and Mathematics"],"dc:title":["Cost Effective Domination in Graphs"],"thesis:degree_discipline":["Mathematical Sciences"],"thesis:degree_level":["Thesis - unrestricted"],"thesis:degree_name":["MS (Master of Science)"]},"updated_at":"2026-07-24T02:20:42Z"}