New bounds for the broadcast domination number of a graph
Richard Brewster; Christina Mynhardt; Laura Teshima
Open Mathematics (2013)
- Volume: 11, Issue: 7, page 1334-1343
- ISSN: 2391-5455
Access Full Article
topAbstract
topHow to cite
topReferences
top- [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 Zbl1066.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 Zbl1089.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] Zbl0418.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 Zbl0907.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] Zbl0393.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] Zbl1222.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] Zbl1175.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] Zbl1081.05084
- [10] Dunbar J., Hedetniemi S.M., Hedetniemi S.T., Broadcasts in trees, 2003, manuscript Zbl1081.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 Zbl1071.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 Zbl0890.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 Zbl0890.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] Zbl1115.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] Zbl1221.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 Zbl1224.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] Zbl1308.90190