Spelling suggestions: "subject:"radial tre""
1 |
Dominating broadcasts in graphsHerke, Sarada Rachelle Anne 29 July 2009 (has links)
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.
|
Page generated in 0.0587 seconds