[Formula presented]-broadcast domination and [Formula presented]-multipacking

Michael A. Henning; Gary MacGillivray; Frank Yang

doi:10.1016/j.dam.2018.04.022

[Formula presented]-broadcast domination and [Formula presented]-multipacking

Michael A. Henning, Gary MacGillivray, Frank Yang

Mathematics and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

Abstract

We generalize broadcast domination by requiring that every vertex must hear a broadcast from each of [Formula presented] different vertices. Some basic theory of [Formula presented]-broadcast domination and its dual problem, [Formula presented]-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 [Formula presented] vertices is at most [Formula presented].

Original language	English
Pages (from-to)	241-251
Number of pages	11
Journal	Discrete Applied Mathematics
Volume	250
DOIs	https://doi.org/10.1016/j.dam.2018.04.022
Publication status	Published - 11 Dec 2018

Keywords

[Formula presented]-broadcast domination
[Formula presented]-multipacking

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2018.04.022

Cite this

@article{4d130e8cafb64887a3bf56ba1a361a9d,

title = "[Formula presented]-broadcast domination and [Formula presented]-multipacking",

abstract = "We generalize broadcast domination by requiring that every vertex must hear a broadcast from each of [Formula presented] different vertices. Some basic theory of [Formula presented]-broadcast domination and its dual problem, [Formula presented]-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 [Formula presented] vertices is at most [Formula presented].",

keywords = "[Formula presented]-broadcast domination, [Formula presented]-multipacking",

author = "Henning, {Michael A.} and Gary MacGillivray and Frank Yang",

note = "Publisher Copyright: {\textcopyright} 2018 Elsevier B.V.",

year = "2018",

month = dec,

day = "11",

doi = "10.1016/j.dam.2018.04.022",

language = "English",

volume = "250",

pages = "241--251",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - [Formula presented]-broadcast domination and [Formula presented]-multipacking

AU - Henning, Michael A.

AU - MacGillivray, Gary

AU - Yang, Frank

PY - 2018/12/11

Y1 - 2018/12/11

N2 - We generalize broadcast domination by requiring that every vertex must hear a broadcast from each of [Formula presented] different vertices. Some basic theory of [Formula presented]-broadcast domination and its dual problem, [Formula presented]-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 [Formula presented] vertices is at most [Formula presented].

AB - We generalize broadcast domination by requiring that every vertex must hear a broadcast from each of [Formula presented] different vertices. Some basic theory of [Formula presented]-broadcast domination and its dual problem, [Formula presented]-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 [Formula presented] vertices is at most [Formula presented].

KW - [Formula presented]-broadcast domination

KW - [Formula presented]-multipacking

UR - http://www.scopus.com/inward/record.url?scp=85047539013&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2018.04.022

DO - 10.1016/j.dam.2018.04.022

M3 - Article

AN - SCOPUS:85047539013

SN - 0166-218X

VL - 250

SP - 241

EP - 251

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

[Formula presented]-broadcast domination and [Formula presented]-multipacking

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this