Maximum boundary independent broadcasts in graphs and trees
Abstract
A broadcast on a connected graph G is a function f : V(G)→{0, 1, ..., diam(G)} such that f(v)≤e(v) (the eccentricity of v) for all v ∈ V. If dG(u, v)≥f(u)+f(v) for any pair of vertices u, v with f(u)>0 and f(v)>0, the broadcast is said to be boundary independent.
We show that the maximum weight αbn(G) of a boundary independent broadcast can be bounded in terms of the independence number α(G), and prove that the maximum boundary independent broadcast problem is NP-hard. We investigate bounds on αbn(T) when T is a tree in terms of its order and the number of vertices of degree at least 3, and determine a sharp upper bound on αbn(T) when T is a caterpillar, giving αbn(T) exactly for certain families of caterpillars. We conclude by describing a polynomial-time algorithm to determine αbn(T) for a given tree T.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2025.13.2.1
References
S. Bessy and D. Rautenbach. Algorithmic aspects of broadcast independence. Disc. Appl. Math. 314 (2022), 142–149.
S. Bessy and D. Rautenbach. Girth, minimum degree, independence, and broadcast independence. Commun. Comb. Optim. 4 (2019), 131–139.
S. Bessy and D. Rautenbach. Relating broadcast independence and independence. Discrete Math. 342 (2019), article 111589.
G. Chartrand, L. Lesniak, and P. Zhang. Graphs and digraphs, 6th ed., CRC Press, New York, 2016.
J.E. Dunbar, D.J. Erwin, T.W. Haynes, S.M. Hedetniemi and S.T. Hedetniemi. Broadcasts in graphs. Discrete Applied Math, 154 (2006), 59–75.
D. Erwin. Cost Domination in Graphs. Doctoral dissertation, Western Michigan University, Kalamazoo, MI, USA, 2001. https://scholarworks.wmich.edu/cgi/viewcontent.cgi?article=2367&context=dissertations&httpsredir=1&referer=.
P. Heggernes and D. Lokshtanov. Optimal broadcast domination in polynomial time. Discrete Mathematics, 36 (2006), 3267-3280.
M.A. Henning, G. MacGillivray, and F. Yang. Broadcast domination in graphs. In T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, editors, Structures of Domination in Graphs, pages 15–46. Springer International Publishing, Cham, Switzerland, 2021.
J.I. Hoepner. Boundary Independent Broadcasts in Graphs. Graduate thesis, University of Victoria, Victoria, BC, Canada, 2022. http://hdl.handle.net/1828/14556.
R.M. Karp. Reducibility among combinatorial problems. In R.E. Miller and J.W. Thatcher, editors, Complexity of computer computations, pages 85–103. Plenum Press, New York, 1972
E. Marchessault and C.M. Mynhardt. Lower boundary independent broadcasts in trees. Discuss. Math. Graph Theory, to appear. Accepted September 12, 2021. https://doi.org/10.7151/dmgt.2434.
C.M. Mynhardt and L. Neilson. A sharp upper bound for the boundary independence broadcast number of a tree. arxiv:2104.02266v2, 2021.
C.M. Mynhardt and L. Neilson. Boundary independent broadcasts in graphs. J. Combin. Math. Combin. Comput., 116 (2021), 79-100.
C.M. Mynhardt and L. Neilson. Comparing Upper Broadcast Domination and Boundary Independence Numbers of Graphs. Trans. Comb., to appear. arxiv:2104.02257, 2021.
C. M. Mynhardt and L. Neilson. Lower bound and exact values for the boundary independence broadcast number of a tree. arxiv:2105.02312v1, 2021.
L. Neilson. Broadcast Independence in Graphs. Doctoral dissertation, University of Victoria, Victoria, BC, Canada, 2019. https://dspace.library.uvic.ca/bitstream/handle/1828/11084/Neilson_Linda_PhD_2019.pdf.
H.N. de Ridder et al. ISGCI: Information System on Graph Classes and Their Inclusions - Graph Classes Listen by Hardness of the Independent Set Problem. https://www.graphclasses.org/classes/problem_Independent_set.html.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.