文章基本信息

标题：Client–server and cost effective sets in graphs
本地全文：下载
作者：Mustapha Chellali ; Teresa W. Haynes ; Stephen T. Hedetniemi 等
期刊名称：AKCE International Journal of Graphs and Combinatorics
印刷版ISSN：0972-8600
出版年度：2018
卷号：15
期号：2
页码：211-218
DOI：10.1016/j.akcej.2017.09.001
语种：English
出版社：Elsevier
摘要：AbstractFor any integerk≥0, a set of verticesSof a graphG=(V,E)isk-cost-effectiveif for everyv∈S,|N(v)∩(V∖S)|≥|N(v)∩S|+k. In this paper we study the minimum cardinality of a maximalk-cost-effective set and the maximum cardinality of ak-cost-effective set. We obtain Gallai-type results involving thek-cost-effective and globalk-offensive alliance parameters, and we provide bounds on the maximumk-cost-effective number. Finally, we considerk-cost-effective sets that are also dominating. We show that computing thek-cost-effective domination number is NP-complete for bipartite graphs. Moreover, we note that not all trees have ak-cost-effective dominating set and give a constructive characterization of those that do.
关键词：KeywordsCost effective setsk-cost-effective setsDominationk-cost effective dominationGlobalk-offensive alliances