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.
| Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-11509 |
| Date | 01 August 2018 |
| Creators | Chellali, Mustapha, Haynes, Teresa W., Hedetniemi, Stephen T. |
| Publisher | Digital Commons @ East Tennessee State University |
| Source Sets | East Tennessee State University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | ETSU Faculty Works |
| Rights | http://creativecommons.org/licenses/by/4.0/ |
Page generated in 0.0017 seconds