Document Type
Article
Publication Date
8-1-2018
Description
For any integer k≥0, a set of vertices S of a graph G=(V,E) is k-cost-effective if for every v∈S,|N(v)∩(V∖S)|≥|N(v)∩S|+k. In this paper we study the minimum cardinality of a maximal k-cost-effective set and the maximum cardinality of a k-cost-effective set. We obtain Gallai-type results involving the k-cost-effective and global k-offensive alliance parameters, and we provide bounds on the maximum k-cost-effective number. Finally, we consider k-cost-effective sets that are also dominating. We show that computing the k-cost-effective domination number is NP-complete for bipartite graphs. Moreover, we note that not all trees have a k-cost-effective dominating set and give a constructive characterization of those that do.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Citation Information
Chellali, Mustapha; Haynes, Teresa W.; and Hedetniemi, Stephen T.. 2018. Client–Server and Cost Effective Sets in Graphs. AKCE International Journal of Graphs and Combinatorics. Vol.15(2). 211-218. https://doi.org/10.1016/j.akcej.2017.09.001 ISSN: 0972-8600
Copyright Statement
2018 Kalasalingam University. Publishing Services by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).