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.

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.0022 seconds