Return to search

Dominating broadcasts in graphs

A broadcast is a function $f:V \rightarrow { 0,...,diam(G)}$ that assigns an integer value to each vertex such that, for each $v\in V$, $f(v)\leq e(v)$, the eccentricity of $v$. The broadcast number of a graph is the minimum value of $\sum_{v\in
V}f(v)$ among all broadcasts $f$ for which each vertex of the graph is within distance $f(v)$ from some vertex $v$ having $f(v)\geq1$. This number is bounded above by the radius of the graph, as well as by its domination number. Graphs for which the broadcast number is equal to the radius are called radial. We prove a new upper bound on the broadcast number of a graph and motivate the study of radial trees by proving a relationship between the broadcast number of a graph and those of its spanning subtrees. We describe some classes of radial trees and then provide a characterization of radial trees, as well as a geometric interpretation of our characterization.

Identiferoai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/1479
Date29 July 2009
CreatorsHerke, Sarada Rachelle Anne
ContributorsMynhardt, C. M.
Source SetsUniversity of Victoria
LanguageEnglish, English
Detected LanguageEnglish
TypeThesis
RightsAvailable to the World Wide Web

Page generated in 0.0018 seconds