Return to search

New results on broadcast domination and multipacking

Let G be a graph and f be a function that maps V to {0,1,2, ..., diam(G)}.
Let V+ be the set of all vertices such that f(v) is positive.
If for every vertex v not in V+ there exists a vertex w in V+ such that
the distance between v and w is at most f(w),
then f is called a dominating broadcast of G.
The cost of the broadcast f is the sum of the values f(v) over all vertices v in V.
The minimum cost of a dominating broadcast is called the broadcast domination number of G.

A subset S of V is a multipacking if, for every v in V and for every integer k which is at least 1 and at most rad(G),
the set S contains at most k vertices at distance at most k from v.
The multipacking number of G is the maximum cardinality of a multipacking of G.

In the first part of the thesis, we describe how linear programming can be used to give a cubic algorithm to find the broadcast domination number and multipacking number of strongly chordal graphs.
Next, we restrict attention to trees, and describe linear time algorithms to compute these numbers. Finally, we introduce k-broadcast domination and k-multipacking, develop the basic theory and give a bound for the 2-broadcast domination number of a tree in terms of its order. / Graduate

Identiferoai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/6627
Date31 August 2015
CreatorsYang, Feiran
ContributorsMacGillivray, Gary, Brewster, R. C.
Source SetsUniversity of Victoria
LanguageEnglish, English
Detected LanguageEnglish
TypeThesis
RightsAvailable to the World Wide Web

Page generated in 0.0018 seconds