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.


    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
    • Combinatorics of Networks and Computation; Funder: European Commission; Code: 734922
    • Deep Drug Discovery and Deployment; Funder: European Commission; Code: PTDC/CCI-BIO/29266/2017

    Consultation statistics

    This page has been seen 578 times.
    This article's PDF has been downloaded 363 times.