• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • No language data
  • Tagged with
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Bounds on Cost Effective Domination Numbers

Haynes, 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 Graphs

Chellali, 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 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.

Page generated in 0.1026 seconds