Upper Broadcast Domination Number of Caterpillars with no Trunks
Abstract
A broadcast on a graph G = (V,E) is a function f : V →{0,…,diam(G)} such that f(v) ≤ eG(v) for every vertex v ∈ V , where diam(G) denotes the diameter of G and eG(v) the eccentricity of v in G. Such a broadcast f is minimal if there does not exist any broadcast g≠f on G such that g(v) ≤ f(v) for all v ∈ V . The upper broadcast domination number of G is the maximum value of ∑ v∈V f(v) among all minimal broadcasts f on G for which each vertex of G is at distance at most f(v) from some vertex v with f(v) ≥ 1. In this paper, we study the minimal dominating broadcasts of caterpillars and give the exact value of the upper broadcast domination number of caterpillars with no trunks.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2024.12.2.6
References
D. Ahmadi, G. H. Fricke, C. Schroeder, S. T. Hedetniemi, R. C. Laskar, Broadcast irredundance in graphs, Congr. Numer. 224 (2015), 17–31.
M. Ahmane, I. Bouchemakh, E. Sopena, On the broadcast independence number of caterpillars, Discrete Applied Math. 244 (2018), 20–35.
https://doi.org/10.1016/j.dam.2018.03.017
M. Ahmane, I. Bouchemakh, E. Sopena, On the Broadcast Independence Number of Locally Uniform 2-Lobsters. Discuss. Math. Graph Theory 44 (2024), 199–229.
https://doi.org/10.7151/dmgt.2443
I. Bouchemakh, N. Fergani, On the upper broadcast domination number, Ars Combin. 130 (2017), 151–161
S. Bouchouika, I. Bouchemakh, E. Sopena, Broadcasts on Paths and Cycles, Discrete Applied Math. 283 (2020), 375–395.
https://doi.org/10.1016/j.dam.2020.01.030
J.E. Dunbar, D.J. Erwin, T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, Broadcasts in graphs, Discrete Applied Math. 154 (2006), 59–75.
https://doi.org/10.1016/j.dam.2005.07.009
D. Erwin, Cost domination in graphs, Ph.D. Dissertation, Western Michigan University, 2001.
D. Erwin, Dominating broadcasts in graphs, Bull. Inst. Combin. Appl. 42 (2004), 89–105.
L. Gemmrich, C.M. Mynhardt, Broadcasts in Graphs: Diametrical Trees, Australas. J. Combin. 69(2) (2017), 243–258.
https://ajc.maths.uq.edu.au/pdf/69/ajc_v69_p243.pdf
M. A. Henning, G. MacGillivray, F. Yang, Broadcast domination in graphs. In T. W. Haynes, S. T. Hedetniemi and M. A. Henning (Eds.), Structures of domination in Graphs, Springer (2020),15–46.
A. Laouar, I. Bouchemakh, E. Sopena, On the Broadcast Independence Number of Circulant Graphs. Discret. Math. Algorithms Appl. 2350053 (2023).
https://doi.org/10.1142/S1793830923500532
C.M. Mynhardt, A. Roux, Dominating and Irredundant Broadcasts in Graphs, Discrete Applied Math. 220 (2017), 80–90.
https://doi.org/10.1016/j.dam.2016.12.012
C. M. Mynhardt, L. Neilson, Comparing Upper Broadcast Domination and Boundary Independence Broadcast Numbers of Graphs. Trans. Comb. 13(1) (2024), 105–126.
https://doi.org/10.22108/toc.2023.127904.1836
S.M. Seager, Dominating Broadcasts of Caterpillars, Ars Combin. 88 (2008), 307–319.
K.W. Soh, K.M. Koh. Broadcast domination in graph products of paths. Australas. J. Combin. 59 (3) (2014), 342–351.
https://ajc.maths.uq.edu.au/pdf/59/ajc_v59_p342.pdf
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.