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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.