Geodesic
Lower boundary independent broadcasts in trees
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 75-99 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 v∈ V if |V|≥2, and f(v)=1 if V={v}. The cost of f is σ(f)=∑_v∈ Vf(v). Let V_f^+={v∈ V:f(v) gt;0}. A vertex u hears f from v∈ V_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 u∈ V_f^+, we say that the broadcast only overlaps in boundaries. A broadcast f is boundary independent if it overlaps only in boundaries. Denote by i_bn(G) the minimum cost of a maximal boundary independent broadcast. We obtain a characterization of maximal boundary independent broadcasts, show that i_bn(T^')≤ i_bn(T) for any subtree T^' of a tree T, and determine an upper bound for i_bn(T) in terms of the broadcast domination number of T. We show that this bound is sharp for an infinite class of trees.
Keywords: broadcast domination, broadcast independence, boundary independence 
@article{DMGT_2024_44_1_a4,
     author = {Marchessault, E.M. and Mynhardt, C.M.},
     title = {Lower boundary independent broadcasts in trees},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {75--99},
     year = {2024},
     volume = {44},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a4/}
}
TY  - JOUR
AU  - Marchessault, E.M.
AU  - Mynhardt, C.M.
TI  - Lower boundary independent broadcasts in trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 75
EP  - 99
VL  - 44
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a4/
LA  - en
ID  - DMGT_2024_44_1_a4
ER  - 
%0 Journal Article
%A Marchessault, E.M.
%A Mynhardt, C.M.
%T Lower boundary independent broadcasts in trees
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 75-99
%V 44
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a4/
%G en
%F DMGT_2024_44_1_a4
Marchessault, E.M.; Mynhardt, C.M. Lower boundary independent broadcasts in trees. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 75-99. http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a4/

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

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

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

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

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

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

[7] G. Chartrand, L. Lesniak and P. Zhang, Graphs &\ Digraphs, Sixth Edition (Chapman and Hall/CRC, Boca Raton, 2016). https://doi.org/10.1201/b19731

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

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

[10] D.J. Erwin, \textrm{Cost Domination in Graphs, PhD Thesis, Western Michigan University} (2001). scholarworks.wmich.edu/dissertations/1365/

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

[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/9781482246582

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

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

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

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

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

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

[19] L. Neilson, \textrm{Broadcast Independence in Graphs, PhD Thesis, University of Victoria} (2019). http://hdl.handle.net/1828/11084