New bounds for the broadcast domination number of a graph

• Autorzy: Richard Brewster , Christina Mynhardt , Laura Teshima
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Broadcast domination; Broadcast number; Irredundance; Multipacking

Kategorie tematyczne

• 05C70: Factorization, matching, partitioning, covering and packing
• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2013
• Tom: 11
• Numer: 7
• Strony: 1334-1343

Daty

wydano

2013-07-01

online

2013-04-26

Twórcy

autor

Richard Brewster

• Department of Mathematics and Statistics, Thompson Rivers University, 900 McGill Road, Kamloops, BC, V2C 0C8, Canada

autor

Christina Mynhardt

• Department of Mathematics and Statistics, University of Victoria, 3800 Finnerty Road, Victoria, BC, V8W 3P4, Canada

autor

Laura Teshima

• Department of Mathematics and Statistics, University of Victoria, 3800 Finnerty Road, Victoria, BC, V8W 3P4, Canada

Bibliografia

• [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
• [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
• [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]
• [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
• [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]
• [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]
• [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]
• [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]
• [10] Dunbar J., Hedetniemi S.M., Hedetniemi S.T., Broadcasts in trees, 2003, manuscript
• [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
• [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
• [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
• [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]
• [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]
• [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
• [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]

Identyfikatory

DOI

10.2478/s11533-013-0234-8