A dominating broadcast on a graph G = (V, E) is a function f: V → {0, 1, ..., diam G} such that f(v) ≤ e(v) (the eccentricity of v) for all v ∈ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0. The cost of a broadcast f is σ(f) = Σv∈V f(v), and the broadcast number λ b (G) is the minimum cost of a dominating broadcast. A set X ⊆ V(G) is said to be irredundant if each x ∈ X dominates a vertex y that is not dominated by any other vertex in X; possibly y = x. The irredundance number ir (G) is the cardinality of a smallest maximal irredundant set of G. We prove the bound λb(G) ≤ 3 ir(G)/2 for any graph G and show that equality is possible for all even values of ir (G). We also consider broadcast domination as an integer programming problem, the dual of which provides a lower bound for λb.
@article{bwmeta1.element.doi-10_2478_s11533-013-0234-8,
author = {Richard Brewster and Christina Mynhardt and Laura Teshima},
title = {New bounds for the broadcast domination number of a graph},
journal = {Open Mathematics},
volume = {11},
year = {2013},
pages = {1334-1343},
zbl = {1266.05109},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-013-0234-8}
}
Richard Brewster; Christina Mynhardt; Laura Teshima. New bounds for the broadcast domination number of a graph. Open Mathematics, Tome 11 (2013) pp. 1334-1343. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-013-0234-8/
[1] Blair J.R.S., Heggernes P., Horton S., Manne F., Broadcast domination algorithms for interval graphs, series-parallel graphs, and trees, In: Proceedings of the Thirty-Fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer., 2004, 169, 55–77 | Zbl 1066.05138
[2] Blair J.R.S., Horton S.B., Broadcast covers in graphs, In: Proceedings of the Thirty-Sixth Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Congr. Numer., 2005, 173, 109–115 | Zbl 1089.05055
[3] Bollobás B., Cockayne E.J., Graph theoretic parameters concerning domination, independence and irredundance, J. Graph Theory, 1979, 3(3), 241–249 http://dx.doi.org/10.1002/jgt.3190030306[Crossref] | Zbl 0418.05049
[4] Chartrand G., Lesniak L., Graphs & Digraphs, 4th ed., Chapman & Hall/CRC, Boca Raton, 2005
[5] Cockayne E.J., Grobler P.J.P., Hedetniemi S.T., McRae A.A., What makes an irredundant set maximal?, J. Combin. Math. Combin. Comput., 1997, 25, 213–223 | Zbl 0907.05032
[6] Cockayne E.J., Hedetniemi S.T., Miller D.J., Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull., 1978, 21(4), 461–468 http://dx.doi.org/10.4153/CMB-1978-079-5[Crossref] | Zbl 0393.05044
[7] Cockayne E.J., Herke S., Mynhardt C.M., Broadcasts and domination in trees, Discrete Math., 2011, 311(13), 1235–1246 http://dx.doi.org/10.1016/j.disc.2009.12.012[WoS][Crossref] | Zbl 1222.05196
[8] Dabney J., Dean B.C., Hedetniemi S.T., A linear-time algorithm for broadcast domination in a tree, Networks, 2009, 53(2), 160–169 http://dx.doi.org/10.1002/net.20275[Crossref] | Zbl 1175.68288
[9] Dunbar J.E., Erwin D.J., Haynes T.W., Hedetniemi S.M., Hedetniemi S.T., Broadcasts in graphs, Discrete Appl. Math., 2006, 154(1), 59–75 http://dx.doi.org/10.1016/j.dam.2005.07.009[Crossref] | Zbl 1081.05084
[10] Dunbar J., Hedetniemi S.M., Hedetniemi S.T., Broadcasts in trees, 2003, manuscript | Zbl 1081.05084
[11] Erwin D.J., Cost Domination in Graphs, PhD thesis, Western Michigan University, Kalamazoo, 2001
[12] Erwin D.J., Dominating broadcasts in graphs, Bull. Inst. Combin. Appl., 2004, 42, 89–105 | Zbl 1071.05056
[13] Haynes T.W., Hedetniemi S.T., Slater P.J., Fundamentals of Domination in Graphs, Monogr. Textbooks Pure Appl. Math., 208, Marcel Dekker, New York, 1998 | Zbl 0890.05002
[14] Haynes T.W., Hedetniemi S.T., Slater P.J. (Eds.), Domination in Graphs, Monogr. Textbooks Pure Appl. Math., 209, Marcel Dekker, New York, 1998 | Zbl 0890.05002
[15] Heggernes P., Lokshtanov D., Optimal broadcast domination in polynomial time, Discrete Math., 2006, 306(24), 3267–3280 http://dx.doi.org/10.1016/j.disc.2006.06.013[Crossref] | Zbl 1115.68115
[16] Herke S.R.A., Dominating Broadcasts in Graphs, MSc thesis, University of Victoria, Victoria, 2007, available at https://dspace.library.uvic.ca:8443/handle/1828/1479
[17] Herke S., Mynhardt C.M., Radial trees, Discrete Math., 2009, 309(20), 5950–5962 http://dx.doi.org/10.1016/j.disc.2009.04.024[Crossref] | Zbl 1221.05051
[18] Lunney S., Trees with Equal Broadcast and Domination Numbers, MSc thesis, University of Victoria, Victoria, 2011, available at http://dspace.library.uvic.ca:8080/handle/1828/3746
[19] Meir A., Moon J.W., Relations between packing and covering numbers of a tree, Pacific J. Math., 1975, 61(1), 225–233 http://dx.doi.org/10.2140/pjm.1975.61.225[Crossref]
[20] Pfaff J.S., Algorithmic Complexities of Domination-Related Graph Parameters, PhD thesis, Clemson University, Clemson, 1984
[21] Seager S.M., Dominating broadcasts of caterpillars, Ars Combin., 2008, 88, 307–319 | Zbl 1224.05381
[22] Shen S., Smith J.C., A decomposition approach for solving a broadcast domination network design problem, Ann. Oper. Res., DOI: 10.1007/s10479-011-0962-8 [Crossref][WoS] | Zbl 1308.90190