Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Open Access

Lower Boundary Independent Broadcasts in Trees

Accepted: 20 Sep 2021
Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English

A broadcast on a connected 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 vV if |V| ≥ 2, and f(v) = 1 if V = {v}. The cost of f is σ (f) = ΣvV f(v). Let V+f = {vV : f(v) > 0}. A vertex u hears f from vV+f if the distance d(u, v) ≤ f(v). When f is a broadcast such that every vertex x that hears f from more than one vertex in V+f also satisfies d(x, u) ≥ f(u) for all uV+f, we say that the broadcast only overlaps in boundaries. A broadcast f is boundary independent if it overlaps only in boundaries. Denote by ibn(G) the minimum cost of a maximal boundary independent broadcast.

We obtain a characterization of maximal boundary independent broadcasts, show that ibn(T′) ≤ ibn(T) for any subtree T′ of a tree T, and determine an upper bound for ibn(T) in terms of the broadcast domination number of T . We show that this bound is sharp for an infinite class of trees.

MSC 2010

[1] M. Ahmane, I. Bouchemakh and É. Sopena, On the broadcast independence of caterpillars, Discrete Appl. Math. 244 (2018) 20–35. https://doi.org/10.1016/j.dam.2018.03.01710.1016/j.dam.2018.03.017Search in Google Scholar

[2] S. Bessy and D. Rautenbach, Relating broadcast independence and independence, Discrete Math. 342 (2019) 111589. https://doi.org/10.1016/j.disc.2019.07.00510.1016/j.disc.2019.07.005Search in Google Scholar

[3] S. Bessy and D. Rautenbach, Girth, minimum degree, independence, and broadcast independence, Commun. Comb. Optim. 4 (2019) 131–139. https://doi.org/10.22049/cco.2019.26346.1098Search in Google Scholar

[4] I. Bouchemakh and M. Zemir, On the broadcast independence number of grid graph, Graphs Combin. 30 (2014) 83–100. https://doi.org/10.1007/s00373-012-1253-010.1007/s00373-012-1253-0Search in Google Scholar

[5] S. Bouchouika, I. Bouchemakh and É. Sopena, Broadcasts on paths and cycles, Discrete Appl. Math. 283 (2020) 375–395. https://doi.org/10.1016/j.dam.2020.01.03010.1016/j.dam.2020.01.030Search in Google Scholar

[6] R.C. Brewster, C.M. Mynhardt and L.E. Teshima, New bounds for the broadcast domination number of a graph, Cent. Eur. J. Math. 11 (2013) 1334–1343. https://doi.org/10.2478/s11533-013-0234-810.2478/s11533-013-0234-8Search in Google Scholar

[7] G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs, Sixth Edition (Chapman and Hall/CRC, Boca Raton, 2016). https://doi.org/10.1201/b1973110.1201/b19731Search in Google Scholar

[8] J.E. Dunbar, D.J. Erwin, T.W. Haynes, S.M. Hedetniemi and S.T. Hedetniemi, Broadcasts in graphs, Discrete Appl. Math. 154 (2006) 59–75. https://doi.org/10.1016/j.dam.2005.07.00910.1016/j.dam.2005.07.009Search in Google Scholar

[9] J. Dunbar, S.M. Hedetniemi and S.T. Hedetniemi, Broadcasts in trees (2003), manuscript.Search in Google Scholar

[10] D.J. Erwin, Cost Domination in Graphs, PhD Thesis, Western Michigan University (2001). scholarworks.wmich.edu/dissertations/1365/Search in Google Scholar

[11] D. Erwin, Dominating broadcasts in graphs, Bull. Inst. Combin. Appl. 42 (2004) 89–105.Search in Google Scholar

[12] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). https://doi.org/10.1201/978148224658210.1201/9781482246582Search in Google Scholar

[13] P. Heggernes and D. Lokshtanov, Optimal broadcast domination in polynomial time, Discrete Math. 306 (2006) 3267–3280. https://doi.org/10.1016/j.disc.2006.06.01310.1016/j.disc.2006.06.013Search in Google Scholar

[14] M.A. Henning, G. MacGillivray and F. Yang, Broadcast domination in graphs, in: Structures of Domination in Graphs, T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Ed(s)), (Springer, Cham, 2020) 15–46. https://doi.org/10.1007/978-3-030-58892-2_210.1007/978-3-030-58892-2_2Search in Google Scholar

[15] S. Herke, Dominating Broadcasts in Graphs, MSc Thesis, University of Victoria (2009). http://hdl.handle.net/1828/1479Search in Google Scholar

[16] S. Herke and C.M. Mynhardt, Radial trees, Discrete Math. 309 (2009) 5950–5962. https://doi.org/10.1016/j.disc.2009.04.02410.1016/j.disc.2009.04.024Search in Google Scholar

[17] C.M. Mynhardt and A. Roux, Dominating and irredundant broadcasts in graphs, Discrete Appl. Math. 220 (2017) 80–90. https://doi.org/10.1016/j.dam.2016.12.01210.1016/j.dam.2016.12.012Search in Google Scholar

[18] C.M. Mynhardt and L. Neilson, Boundary independent broadcasts in graphs, J. Combin. Math. Combin. Comput. 116 (2021) 79–100.Search in Google Scholar

[19] L. Neilson, Broadcast Independence in Graphs, PhD Thesis, University of Victoria (2019). http://hdl.handle.net/1828/11084Search in Google Scholar

• A Note About Monochromatic Components in Graphs of Large Minimum Degree

Recommended articles from Trend MD