Applicable analysis and discrete mathematics

Vol. 12, num. 1, p. 205-223

DOI: 10.2298/AADM1801205C

Date of publication: 2018-04-20

Abstract:

Limited dominating broadcasts were proposed as a variant of dominating broadcasts, where the broadcast function is upper bounded. As a natural extension of domination, we consider dominating 2-broadcasts along with the associated parameter, the dominating 2-broadcast number. We prove that computing the dominating 2-broadcast number is a NP-complete problem, but can be achieved in linear time for trees. We also give an upper bound for this parameter, that is tight for graphs as large as desired.]]>

Applicable analysis and discrete mathematics

Vol. 10, p. 46-64

DOI: 10.2298/AADM160406007C

Date of publication: 2016-04-25

Abstract:

A k quasip erfect dominating set of a connected graph G is a vertex subset S such that every vertex not in S is adjacent to at least one and at most k vertices in S . The cardinality of a minimum k-quasip erfect dominating set in G is denoted by 1 k ( G ) . These graph parameters were rst intro duced by Chellali et al. (2013) as a generalization of b oth the p erfect domination numb er 11 ( G ) and the domination numb er ( G ) . The study of the so-called quasip erfect domination chain 11 ( G ) 12 ( G ) 1 ( G ) = ( G ) enable us to analyze how far minimum dominating sets are from b eing p erfect. In this pap er, we provide, for any tree T and any p ositive integer k , a tight upp er b ound of 1 k ( T ) . We also prove that there are trees satisfying all p ossible equalities and inequalities in this chain. Finally a linear algorithm for computing 1 k ( T ) in any tree T is presente

A k quasip erfect dominating set of a connected graph G is a vertex subset S such that every vertex not in S is adjacent to at least one and at most k vertices in S . The cardinality of a minimum k-quasip erfect dominating set in G is denoted by 1 k ( G ) . These graph parameters were rst intro duced by Chellali et al. (2013) as a generalization of b oth the p erfect domination numb er 11 ( G ) and the domination numb er ( G ) . The study of the so-called quasip erfect domination chain 11 ( G ) 12 ( G ) 1 ( G ) = ( G ) enable us to analyze how far minimum dominating sets are from b eing p erfect. In this pap er, we provide, for any tree T and any p ositive integer k , a tight upp er b ound of 1 k ( T ) . We also prove that there are trees satisfying all p ossible equalities and inequalities in this chain. Finally a linear algorithm for computing 1 k ( T ) in any tree T is presente]]>