Broadcast domination and multipacking: bounds and the integrality gap

MaRDI QIDQ5197586zbMATH OpenFDO

Authors Laurent Beaudou, Richard C. Brewster, Florent Foucaud

Publication date 19 September 2019

Full work available at URL https://arxiv.org/abs/1803.02550, http://ajc.maths.uq.edu.au/pdf/74/ajc_v74_p086.pdf

maximum weight packing minimum cost coverings

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: The dual concepts of coverings and packings are well studied in graph theory. Coverings of graphs with balls of radius one and packings of vertices with pairwise distances at least two are the well-known concepts of domination and independence, respectively. In 2001, Erwin introduced emph{broadcast domination} in graphs, a covering problem using balls of various radii, where the cost of a ball is its radius. The minimum cost of a dominating broadcast in a graph

G

is denoted by

g a m m a_{b} (G)

. The dual (in the sense of linear programming) of broadcast domination is emph{multipacking}: a multipacking is a set

P s u b s e t e q V (G)

such that for any vertex

v

and any positive integer

r

, the ball of radius

r

around

v

contains at most

r

vertices of

P

. The maximum size of a multipacking in a graph

G

is denoted by

m p (G)

. Naturally,

m p (G) l e q g a m m a_{b} (G)

. Hartnell and Mynhardt proved that

g a m m a_{b} (G) l e q 3 m p (G) - 2

(whenever

m p (G) g e q 2

). In this paper, we show that

g a m m a_{b} (G) l e q 2 m p (G) + 3

. Moreover, we conjecture that this can be improved to

g a m m a_{b} (G) l e q 2 m p (G)

(which would be sharp).

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Broadcast domination and multipacking: bounds and the integrality gap

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5197586)