"Client–Server and Cost Effective Sets in Graphs" by Mustapha Chellali, Teresa W. Haynes et al.
 

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.

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/).

Creative Commons License

Creative Commons Attribution 4.0 International License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Plum Print visual indicator of research metrics
PlumX Metrics
  • Citations
    • Citation Indexes: 5
  • Usage
    • Downloads: 29
    • Abstract Views: 2
  • Captures
    • Readers: 6
see details

Share

COinS