1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

On the Broadcast Independence Number of Locally Uniform 2-Lobsters

Published Online: 10 Jan 2022
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 08 Dec 2020
Accepted: 11 Nov 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

Let G be a simple undirected graph. A broadcast on G is a function f : V (G) → ℕ such that f(v) ≤ eG(v) holds for every vertex v of G, where eG(v) denotes the eccentricity of v in G, that is, the maximum distance from v to any other vertex of G. The cost of f is the value cost(f) = Σv∈V(G) f(v). A broadcast f on G is independent if for every two distinct vertices u and v in G with f(u) > 0 and f(v) > 0, dG(u, v) > max{f(u), f(v)}, where dG(u, v) denotes the distance between u and v in G. The broadcast independence number of G is then defined as the maximum cost of an independent broadcast on G.

A caterpillar is a tree such that, after the removal of all leaf vertices, the remaining graph is a non-empty path. A lobster is a tree such that, after the removal of all leaf vertices, the remaining graph is a caterpillar. In [M. Ahmane, I. Bouchemakh and E. Sopena, On the broadcast independence number of caterpillars, Discrete Appl. Math. 244 (2018) 20–35], we studied independent broadcasts of caterpillars. In this paper, carrying on with this line of research, we consider independent broadcasts of lobsters and give an explicit formula for the broadcast independence number of a family of lobsters called locally uniform 2-lobsters.

Keywords

MSC 2010

[1] M. Ahmane, Sur le Nombre de Broadcast indépendance de Quelques Classes d’arbres, PhD Thesis (in French), University of Sciences and Technology (Houari Boumediene USTHB, 2020). Search in Google Scholar

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

[3] L. Beaudou and R.C. Brewster, On the multipacking number of grid graphs, Discrete Math. Theor. Comput. Sci. 21 (2019) #23. https://doi.org/10.23638/DMTCS-21-3-23 Search in Google Scholar

[4] L. Beaudou, R.C. Brewster and F. Foucaud, Broadcast domination and multipacking: bounds and the integrality gap, Australas. J. Combin. 74 (2019) 86–97. Search in Google Scholar

[5] S. Bessy and D. Rautenbach, Algorithmic aspects of broadcast independence (2018). arXiv:1809.07248. Search in Google Scholar

[6] 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.005 Search in Google Scholar

[7] S. Bessy and D. Rautenbach, Girth, minimum degree, independence, and broadcast independence, Commun. Comb. Optim. 4 (2019) 131–139. Search in Google Scholar

[8] J.R.S. Blair, P. Heggernes, S. Horton and F. Manne, Broadcast domination algorithms for interval graphs, series-parallel graphs and trees, Congr. Num. 169 (2004) 55–77. Search in Google Scholar

[9] I. Bouchemakh and N. Fergani, On the upper broadcast domination number, Ars Combin. 130 (2017) 151–161. Search in Google Scholar

[10] I. Bouchemakh and R. Sahbi, On a conjecture of Erwin, Stud. Inform. Univ. 9 (2011) 144–151. Search in Google Scholar

[11] 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-0 Search in Google Scholar

[12] B. Brešar and S. Špacapan, Broadcast domination of products of graphs, Ars Combin. 92 (2009) 303–320. Search in Google Scholar

[13] R.C. Brewster, G. MacGillivray and F. Yang, Broadcast domination and multipacking in strongly chordal graphs, Discrete Appl. Math. 261 (2019) 108–118. https://doi.org/10.1016/j.dam.2018.08.02110.1016/j.dam.2018.08.021 Search in Google Scholar

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

[15] E.J. Cockayne, S. Herke and C.M. Mynhardt, Broadcasts and domination in trees, Discrete Math. 311 (2011) 1235–1246. https://doi.org/10.1016/j.disc.2009.12.01210.1016/j.disc.2009.12.012 Search in Google Scholar

[16] J. Dabney, B.C. Dean, and S.T. Hedetniemi, A linear-time algorithm for broadcast domination in a tree, Networks 53 (2009) 160–169. https://doi.org/10.1002/net.2027510.1002/net.20275 Search in Google Scholar

[17] 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.009 Search in Google Scholar

[18] D.J. Erwin, Cost domination in graphs (PhD Thesis, Western Michigan University, 2001). Search in Google Scholar

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

[20] L. Gemmrich and C.M. Mynhardt, Broadcasts in graphs: Diametrical trees, Australas. J. Combin. 69 (2017) 243–258. Search in Google Scholar

[21] B.L. Hartnell and C.M. Mynhardt, On the di erence between broadcast and multi-packing numbers of graphs, Util. Math. 94 (2014) 19–29. Search in Google Scholar

[22] S.T. Hedetniemi, Unsolved algorithmic problems on trees, AKCE Int. J. Graphs Comb. 3 (2006) 1–37. https://doi.org/10.1080/09728600.2006.12088803 Search in Google Scholar

[23] 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.013 Search in Google Scholar

[24] 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.024 Search in Google Scholar

[25] S. Lunney and C.M. Mynhardt, More trees with equal broadcast and domination numbers, Australas. J. Combin. 61 (2015) 251–272. Search in Google Scholar

[26] 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.012 Search in Google Scholar

[27] C.M. Mynhardt and L. Teshima, Broadcasts and multipackings in trees, Util. Math. 104 (2017) 227–242. Search in Google Scholar

[28] C.M. Mynhardt and J. Wodlinger, A class of trees with equal broadcast and domination numbers, Australas. J. Combin. 56 (2013) 3–22. Search in Google Scholar

[29] C.M. Mynhardt and J. Wodlinger, Uniquely radial trees, J. Combin. Math. Combin. Comput. 93 (2015) 131–152. Search in Google Scholar

[30] S.M. Seager, Dominating Broadcasts of Caterpillars, Ars Combin. 88 (2008) 307– 319. Search in Google Scholar

[31] K.W. Soh and K.M. Koh, Broadcast domination in graph products of paths, Australas. J. Combin. 59 (2014) 342–351. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo