Article in volume
Authors:
Julia Ingrid Hoepner
Department of Mathematics and Statistics
University of Victoria
Victoria, BC
email: julesihoepner@gmail.com
Title:
Lower boundary independent and hearing independent broadcasts in graphs
PDFSource:
Discussiones Mathematicae Graph Theory 45(2) (2025) 653-675
Received: 2023-05-31 , Revised: 2024-04-26 , Accepted: 2024-05-01 , Available online: 2024-06-13 , https://doi.org/10.7151/dmgt.2546
Abstract:
A broadcast on a connected graph $G$ with vertex set $V(G)$ is a
function $f:V(G)\rightarrow \{0, 1,\dots, \operatorname{diam}(G)\}$ such that
$f(v)\leq e(v)$ (the eccentricity of $v$) for all $v\in V(G)$. A vertex $v$ is
said to be broadcasting if $f(v)>0$, with the set of all such vertices
denoted $V_f^+$. A vertex $u$ hears $f$ from $v\in V_f^+$ if
$d_G(u, v)\leq f(v)$. The broadcast $f$ is hearing independent if no
broadcasting vertex hears another. If, in the broadcast $f$, any vertex $u$ that
hears $f$ from multiple broadcasting vertices satisfies $f(v)\leq d_G(u, v)$
for all $v\in V_f^+$, it is said to be boundary independent.
The cost of $f$ is $\sigma(f)=\sum_{v\in V(G)}f(v)$.
The minimum cost of a maximal boundary independent broadcast on $G$, called the
lower bn-independence number, is denoted by $i_{bn}(G)$. The
lower h-independence number $i_h(G)$ is defined analogously for
hearing independent broadcasts. We prove that for an arbitrary connected graph
$G$, either parameter equals the minimum of the corresponding parameter among
that of the spanning trees of $G$. We use these results to prove that
$i_{bn}(G)\leq i_h(G)$ for all graphs $G$. We also show that $i_h(G)/i_{bn}(G)$
is bounded.
Keywords:
broadcast domination, broadcast independence, boundary independence, hearing independence
References:
- 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 - S. Bessy and D. Rautenbach, Relating broadcast independence and independence, Discrete Math. 342(12) (2019) 111589.
https://doi.org/10.1016/j.disc.2019.07.005 - G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs, 6th Ed. (Chapman & Hall/CRC, New York, 2015).
https://doi.org/10.1201/b19731 - 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 - D.J. Erwin, Cost Domination in Graphs, PhD Thesis (Western Michigan University, Kalamazoo, MI, USA, 2001).
- M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman & Co., New York, NY, USA, 1979).
- P. Heggernes and D. Lokshtanov, Optimal broadcast domination in polynomial time, Discrete Math. 36 (2006) 3267–3280.
https://doi.org/10.1016/j.disc.2006.06.013 - S. Herke and C.M. Mynhardt, Radial trees, Discrete Math. 309 (2009) 5950–5962.
https://doi.org/10.1016/j.disc.2009.04.024 - 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)), Dev. Math. 66, (Springer, Cham, Switzerland, 2021) 15–46.
https://doi.org/10.1007/978-3-030-58892-2_2 - J.I. Hoepner, Boundary Independent Broadcasts in Graphs, Master's Thesis (University of Victoria, Victoria, BC, Canada, 2022).
- E. Marchessault and C.M. Mynhardt, Lower boundary independent broadcasts in trees, Discuss. Math. Graph Theory 44 (2024) 75–99.
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 (2021).
arXiv: 2104.02266v2 - 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 broadcast numbers of graphs, Trans. Comb. 13 (2024) 105–126.
https://doi.org/10.22108/toc.2023.127904.1836 - C.M. Mynhardt and L. Neilson, Lower bound and exact values for the boundary independence broadcast number of a tree (2021).
arXiv: 2105.02312v1 - L. Neilson, Broadcast Independence in Graphs, PhD Thesis (University of Victoria, Victoria, BC, Canada, 2019).
Close