Spelling suggestions: "subject:"cost effective set""
1 
Bounds on Cost Effective Domination NumbersHaynes, Teresa W., Hedetniemi, Stephen T., McCoy, Tabitha L., Rodriguez, Tony K. 22 September 2016 (has links)
A vertex υ in a set S is said to be cost effective if it is adjacent to at least as many vertices in V\S as it is in S and is very cost effective if it is adjacent to more vertices in V\S than to vertices in S. A dominating set S is (very) cost effective if every vertex in S is (very) cost effective. The minimum cardinality of a (very) cost effective dominating set of G is the (very) cost effective domination number of G. Our main results include a quadratic upper bound on the very cost effective domination number of a graph in terms of its domination number. The proof of this result gives a linear upper bound for hereditarily sparse graphs which include trees. We show that no such linear bound exists for graphs in general, even when restricted to bipartite graphs. Further, we characterize the extremal trees attaining the bound. Noting that the very cost effective domination number is bounded below by the domination number, we show that every value of the very cost effective domination number between these lower and upper bounds for trees is realizable. Similar results are given for the cost effective domination number.

2 
Client–Server and Cost Effective Sets in GraphsChellali, Mustapha, Haynes, Teresa W., Hedetniemi, Stephen T. 01 August 2018 (has links)
For any integer k≥0, a set of vertices S of a graph G=(V,E) is kcosteffective if for every v∈S,N(v)∩(V∖S)≥N(v)∩S+k. In this paper we study the minimum cardinality of a maximal kcosteffective set and the maximum cardinality of a kcosteffective set. We obtain Gallaitype results involving the kcosteffective and global koffensive alliance parameters, and we provide bounds on the maximum kcosteffective number. Finally, we consider kcosteffective sets that are also dominating. We show that computing the kcosteffective domination number is NPcomplete for bipartite graphs. Moreover, we note that not all trees have a kcosteffective dominating set and give a constructive characterization of those that do.

Page generated in 0.1026 seconds