José Cáceres ; Carmen Hernando ; Mercè Mora ; Ignacio M. Pelayo ; María Luz Puertas - General bounds on limited broadcast domination

dmtcs:4054 - Discrete Mathematics & Theoretical Computer Science, October 29, 2018, vol. 20 no. 2 - https://doi.org/10.23638/DMTCS-20-2-13
General bounds on limited broadcast dominationArticle

Authors: José Cáceres ; Carmen Hernando ; Mercè Mora ORCID; Ignacio M. Pelayo ; María Luz Puertas

Dominating broadcasting is a domination-type structure that models a transmission antenna network. In this paper, we study a limited version of this structure, that was proposed as a common framework for both broadcast and classical domination. In this limited version, the broadcast function is upper bounded by an integer $k$ and the minimum cost of such function is the dominating $k$-broadcast number. Our main result is a unified upper bound on this parameter for any value of $k$ in general graphs, in terms of both $k$ and the order of the graph. We also study the computational complexity of the associated decision problem.

Comment: 18 pages, 8 figures


Volume: vol. 20 no. 2
Section: Graph Theory
Published on: October 29, 2018
Accepted on: October 17, 2018
Submitted on: November 7, 2017
Keywords: Mathematics - Combinatorics, 05C69
Funding:
    Source : OpenAIRE Graph
  • Deep Drug Discovery and Deployment; Funder: Fundação para a Ciência e a Tecnologia, I.P.; Code: PTDC/CCI-BIO/29266/2017
  • Combinatorics of Networks and Computation; Funder: European Commission; Code: 734922

Consultation statistics

This page has been seen 903 times.
This article's PDF has been downloaded 567 times.