k-broadcast domination and k-multipacking

We generalize broadcast domination by requiring that every vertex must hear a broadcast from each of k different vertices. Some basic theory of k-broadcast domination and its dual problem, k-multipacking, is developed. We then focus on 2-broadcast domination and show that the 2-broadcast domination...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2018-12, Vol.250, p.241-251
Main Authors: Henning, Michael A., MacGillivray, Gary, Yang, Frank
Format: Article
Language:English
Subjects:
[formula omitted]-broadcast domination
[formula omitted]-multipacking
Apexes
Applied mathematics
Graph theory
Mathematical problems
Number theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We generalize broadcast domination by requiring that every vertex must hear a broadcast from each of k different vertices. Some basic theory of k-broadcast domination and its dual problem, k-multipacking, is developed. We then focus on 2-broadcast domination and show that the 2-broadcast domination number is at most three times the broadcast domination number, but can differ by any additive amount from twice the broadcast domination number. It is shown that the 2-broadcast domination number of a connected graph with n vertices is at most 4n5.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2018.04.022