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

Abstract

top
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.

How to cite

top

Richard Brewster, Christina Mynhardt, and Laura Teshima. "New bounds for the broadcast domination number of a graph." Open Mathematics 11.7 (2013): 1334-1343. <http://eudml.org/doc/269027>.

@article{RichardBrewster2013,
abstract = {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.},
author = {Richard Brewster, Christina Mynhardt, Laura Teshima},
journal = {Open Mathematics},
keywords = {Broadcast domination; Broadcast number; Irredundance; Multipacking; broadcast domination; broadcast number; irredundance; multipacking},
language = {eng},
number = {7},
pages = {1334-1343},
title = {New bounds for the broadcast domination number of a graph},
url = {http://eudml.org/doc/269027},
volume = {11},
year = {2013},
}

TY - JOUR
AU - Richard Brewster
AU - Christina Mynhardt
AU - Laura Teshima
TI - New bounds for the broadcast domination number of a graph
JO - Open Mathematics
PY - 2013
VL - 11
IS - 7
SP - 1334
EP - 1343
AB - 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.
LA - eng
KW - Broadcast domination; Broadcast number; Irredundance; Multipacking; broadcast domination; broadcast number; irredundance; multipacking
UR - http://eudml.org/doc/269027
ER -

References

top
  1. [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. [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. [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. [4] Chartrand G., Lesniak L., Graphs & Digraphs, 4th ed., Chapman & Hall/CRC, Boca Raton, 2005 
  5. [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. [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. [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. [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. [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. [10] Dunbar J., Hedetniemi S.M., Hedetniemi S.T., Broadcasts in trees, 2003, manuscript Zbl1081.05084
  11. [11] Erwin D.J., Cost Domination in Graphs, PhD thesis, Western Michigan University, Kalamazoo, 2001 
  12. [12] Erwin D.J., Dominating broadcasts in graphs, Bull. Inst. Combin. Appl., 2004, 42, 89–105 Zbl1071.05056
  13. [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. [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. [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. [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. [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. [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. [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. [20] Pfaff J.S., Algorithmic Complexities of Domination-Related Graph Parameters, PhD thesis, Clemson University, Clemson, 1984 
  21. [21] Seager S.M., Dominating broadcasts of caterpillars, Ars Combin., 2008, 88, 307–319 Zbl1224.05381
  22. [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

NotesEmbed ?

top

You must be logged in to post comments.