Article in volume
Authors:
Elise Marchessault
Department of Mathematics and Statistics
University of Victoria, Victoria, BC
email: elisemarchessault@uvic.ca
Title:
Lower boundary independent broadcasts in trees
PDFSource:
Discussiones Mathematicae Graph Theory 44(1) (2024) 75-99
Received: 2021-03-24 , Revised: 2021-09-16 , Accepted: 2021-09-20 , Available online: 2021-09-29 , https://doi.org/10.7151/dmgt.2434
Abstract:
A broadcast on a connected graph $G=(V,E)$ is a function $f:V\rightarrow
\{0,1,\dots, \mathrm{diam}(G)\}$ such that $f(v)\leq e(v)$ (the eccentricity
of $v$) for all $v\in V$ if $|V|\geq2$, and $f(v)=1$ if $V=\{v\}$. The cost of
$f$ is $\sigma(f)=\sum_{v\in V}f(v)$. Let $V_{f}^{+}=\{v\in V:f(v)>0\}$.
A vertex $u$ hears $f$ from $v\in V_{f}^{+}$ if the distance $d(u,v)\leq 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)\geq f(u)$ for all
$u\in 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_{\mathrm{bn}}(G)$ the minimum cost of a maximal boundary
independent broadcast.
We obtain a characterization of maximal boundary independent broadcasts, show
that $i_{\mathrm{bn}}(T^{\prime})\leq i_{\mathrm{bn}}(T)$ for any
subtree $T^{\prime}$ of a tree $T$, and determine an upper bound for
$i_{\mathrm{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
References:
- 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 - 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 - 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 - 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 - 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 - 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 - G. Chartrand, L. Lesniak and P. Zhang, Graphs \&\ Digraphs, Sixth Edition (Chapman and Hall/CRC, Boca Raton, 2016).
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 - J. Dunbar, S.M. Hedetniemi and S.T. Hedetniemi, Broadcasts in trees (2003), manuscript.
- D.J. Erwin, Cost Domination in Graphs, PhD Thesis, Western Michigan University (2001).
scholarworks.wmich.edu/dissertations/1365/ - D. Erwin, Dominating broadcasts in graphs, Bull. Inst. Combin. Appl. 42 (2004) 89–105.
- 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 - 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 - 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 - S. Herke, Dominating Broadcasts in Graphs, MSc Thesis, University of Victoria (2009).
http://hdl.handle.net/1828/1479 - S. Herke and C.M. Mynhardt, Radial trees, Discrete Math. 309 (2009) 5950–5962.
https://doi.org/10.1016/j.disc.2009.04.024 - 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 - C.M. Mynhardt and L. Neilson, Boundary independent broadcasts in graphs, J. Combin. Math. Combin. Comput. 116 (2021) 79–100.
- L. Neilson, Broadcast Independence in Graphs, PhD Thesis, University of Victoria (2019).
http://hdl.handle.net/1828/11084
Close