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
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/6627 |
| Date | 31 August 2015 |
| Creators | Yang, Feiran |
| Contributors | MacGillivray, Gary, Brewster, R. C. |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web |
Page generated in 0.0023 seconds