On the broadcast independence number of locally uniform 2-lobsters

Ahmane, Messaouda ; Bouchemakh, Isma  ; Sopena, Éric

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 199-230

Résumé

Let G be a simple undirected graph. A broadcast on G is a function f : V(G)→ℕ such that f(v)≤ e_G(v) holds for every vertex v of G, where e_G(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) gt;0 and f(v) gt;0, d_G(u,v) gt;max{f(u),f(v)}, where d_G(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.

Détail

Keywords: independence, broadcast independence, lobster

Bibliographie

[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).

[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.017

[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

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

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

[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.005

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

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

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

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

[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-0

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

[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.021

[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-8

[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.012

[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.20275

[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.009

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

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

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

[21] B.L. Hartnell and C.M. Mynhardt, On the difference between broadcast and multipacking numbers of graphs, Util. Math. 94 (2014) 19–29.

[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

[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.013

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

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

[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.012

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

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

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

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

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