{"id":{"repo_id":"etsu","oai_identifier":"oai:dc.etsu.edu:etd-3726"},"canonical_url":"https://search.ndltd.org/etd/etsu/oai:dc.etsu.edu:etd-3726","repository":{"repo_id":"etsu","name":"East Tennessee State University","base_url":"https://dc.etsu.edu/do/oai/"},"display":{"title":"Very Cost Effective Domination in Graphs","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Rodriguez, Tony K"],"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":2014,"date_issued":"2014-05-01T07:00:00Z","date_published":"2014-05-01T07:00:00Z","updated_at":"2026-11-19T07:54:11Z","subjects":["very cost effective domination","very cost effective domination number","Discrete Mathematics and Combinatorics","Mathematics"],"languages":[],"rights":["Copyright by the authors."],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://dc.etsu.edu/etd/2345","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://dc.etsu.edu/etd/2345","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":"https://dc.etsu.edu/context/etd/article/3726/viewcontent/RodriquezT042214f.pdf","download_label":"Download PDF","download_source":"dc:identifier","access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://dc.etsu.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adc.etsu.edu%3Aetd-3726","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Rodriguez, Tony K"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2014-04-07T07:00:00Z"]},{"key":"dc:date.issued","label":"Date","values":["2014-05-01T07: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":["very cost effective domination","very cost effective domination number","Discrete Mathematics and Combinatorics","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/3726/viewcontent/RodriquezT042214f.pdf","https://dc.etsu.edu/etd/2345"]}]},{"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, 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."]},{"key":"dc:title","label":"Title","values":["Very Cost Effective Domination in Graphs"]}]}],"canonical_facts":{"dc:creator":["Rodriguez, Tony K"],"dc:date.available":["2014-04-07T07:00:00Z"],"dc:date.issued":["2014-05-01T07: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, 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."],"dc:identifier":["https://dc.etsu.edu/context/etd/article/3726/viewcontent/RodriquezT042214f.pdf","https://dc.etsu.edu/etd/2345"],"dc:rights":["Copyright by the authors."],"dc:subject":["very cost effective domination","very cost effective domination number","Discrete Mathematics and Combinatorics","Mathematics"],"dc:title":["Very 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-11-19T07:54:11Z"}