Loading...
Loading...

Go to the content (press return)

Dominating 2-broadcast in graphs: complexity, bounds and extremal graphs

Author
Cáceres, José; Hernando, M.; Mora, M.; Pelayo, I. M.; Puertas, M. Luz
Type of activity
Journal article
Journal
Applicable analysis and discrete mathematics
Date of publication
2018-04-20
Volume
12
Number
1
First page
205
Last page
223
DOI
https://doi.org/10.2298/AADM1801205C Open in new window
Repository
http://hdl.handle.net/2117/117013 Open in new window
URL
http://pefmath.etf.rs/vol12num1/AADM-Vol12-No1-205-223.pdf Open in new window
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.
Citation
Cáceres, José, Hernando, M., Mora, M., Pelayo, I. M., Puertas, M. L. Dominating 2-broadcast in graphs: complexity, bounds and extremal graphs. "Applicable analysis and discrete mathematics", 20 Abril 2018, vol. 12, núm. 1, p. 205-223.
Keywords
Broadcast, NP-complete decision problem, domination
Group of research
COMBGRAPH - Combinatorics, Graph Theory and Applications
DCG - Discrete and Combinatorial Geometry

Participants

Attachments