Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.akcej.2017.09.001 | AKCE International Journal of Graphs and Combinatorics |
Keywords | DocType | Volume |
Cost effective sets,
k-cost-effective sets,Domination,
k-cost effective domination,Global k-offensive alliances | Journal | 15 |
Issue | ISSN | Citations |
2 | 0972-8600 | 0 |
PageRank | References | Authors |
0.34 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mustapha Chellali | 1 | 188 | 38.24 |
| Teresa W. Haynes | 2 | 774 | 94.22 |
| Stephen T. Hedetniemi | 3 | 1575 | 289.01 |