Return to search

Client–Server and Cost Effective Sets in Graphs

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.

Identiferoai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-11509
Date01 August 2018
CreatorsChellali, Mustapha, Haynes, Teresa W., Hedetniemi, Stephen T.
PublisherDigital Commons @ East Tennessee State University
Source SetsEast Tennessee State University
Detected LanguageEnglish
Typetext
Formatapplication/pdf
SourceETSU Faculty Works
Rightshttp://creativecommons.org/licenses/by/4.0/

Page generated in 0.0017 seconds