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

dmtcs:4054 - Discrete Mathematics & Theoretical Computer Science, October 29, 2018, vol. 20 no. 2
General bounds on limited broadcast domination

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

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.


Source : oai:arXiv.org:1609.05675
Volume: vol. 20 no. 2
Section: Graph Theory
Published on: October 29, 2018
Submitted on: November 7, 2017
Keywords: Mathematics - Combinatorics,05C69


Versions

Share

Consultation statistics

This page has been seen 27 times.
This article's PDF has been downloaded 11 times.