Broadcasts in Graphs
Document Type
Article
Publication Date
1-1-2006
Description
We say that a function f:V→{0,1,...,diam(G)} is a broadcast if for every vertex v∈V, f(v)≤e(v), where diam(G) denotes the diameter of G and e(v) denotes the eccentricity of v. The cost of a broadcast is the value f(V)=∑v∈Vf(v). In this paper we introduce and study the minimum and maximum costs of several types of broadcasts in graphs, including dominating, independent and efficient broadcasts.
Citation Information
Dunbar, Jean; Erwin, David J.; Haynes, Teresa W.; Hedetniemi, Sandra M.; and Hedetniemi, Stephen T.. 2006. Broadcasts in Graphs. Discrete Applied Mathematics. Vol.154(1). 59-75. https://doi.org/10.1016/j.dam.2005.07.009 ISSN: 0166-218X