Article in volume
Authors:
Éric Sopena
Université de Bordeaux, LaBRI UMR 5800, 351, cours de la Libération, F-33405 Talence Cedex
email: eric.sopena@labri.fr
Title:
On the broadcast independence number of locally uniform 2-lobsters
PDFSource:
Discussiones Mathematicae Graph Theory 44(1) (2024) 199-230
Received: 2020-12-08 , Revised: 2021-11-10 , Accepted: 2021-11-11 , Available online: 2021-12-15 , https://doi.org/10.7151/dmgt.2443
Abstract:
Let $G$ be a simple undirected graph. A broadcast on $G$ is a function
$f : V(G)\rightarrow\mathbb{N}$ such that $f(v)\le e_G(v)$ holds for every vertex
$v$ of $G$, where $e_G(v)$ denotes the eccentricity of $v$ in $G$, that is,
the maximum distance from $v$ to any other vertex of $G$. The cost of $f$ is
the value \cost$(f)=\sum_{v\in V(G)}f(v)$. A broadcast $f$ on $G$ is independent
if for every two distinct vertices $u$ and $v$ in $G$ with $f(u)>0$ and
$f(v)>0$, $d_G(u,v)>\max\{f(u),f(v)\}$, where $d_G(u,v)$ denotes the distance
between $u$ and $v$ in $G$. The broadcast independence number of $G$ is then
defined as the maximum cost of an independent broadcast on $G$.
A caterpillar is a tree such that, after the removal of all leaf vertices, the
remaining graph is a non-empty path. A lobster is a tree such that, after the
removal of all leaf vertices, the remaining graph is a caterpillar. In
[M. Ahmane, I. Bouchemakh and E. Sopena, On the broadcast independence
number of caterpillars, Discrete Appl. Math. 244 (2018) 20–35], we studied
independent broadcasts of caterpillars. In this paper, carrying on with this
line of research, we consider independent broadcasts of lobsters and give an
explicit formula for the broadcast independence number of a family of lobsters
called locally uniform $2$-lobsters.
Keywords:
independence, broadcast independence, lobster
References:
- M. Ahmane, Sur le Nombre de Broadcast indépendance de Quelques Classes d'arbres, PhD Thesis (in French), University of Sciences and Technology (Houari Boumediene USTHB, 2020).
- M. Ahmane, I. Bouchemakh and É. Sopena, On the broadcast independence number of caterpillars, Discrete Appl. Math. 244 (2018) 20–35.
https://doi.org/10.1016/j.dam.2018.03.017 - L. Beaudou and R.C. Brewster, On the multipacking number of grid graphs, Discrete Math. Theor. Comput. Sci. 21 (2019) #23.
https://doi.org/10.23638/DMTCS-21-3-23 - L. Beaudou, R.C. Brewster and F. Foucaud, Broadcast domination and multipacking: bounds and the integrality gap, Australas. J. Combin. 74 (2019) 86–97.
- S. Bessy and D. Rautenbach, Algorithmic aspects of broadcast independence (2018).
arXiv: 1809.07248. - 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.
- J.R.S. Blair, P. Heggernes, S. Horton and F. Manne, Broadcast domination algorithms for interval graphs, series-parallel graphs and trees, Congr. Num. 169 (2004) 55–77.
- I. Bouchemakh and N. Fergani, On the upper broadcast domination number, Ars Combin. 130 (2017) 151–161.
- I. Bouchemakh and R. Sahbi, On a conjecture of Erwin, Stud. Inform. Univ. 9 (2011) 144–151.
- 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 - B. Brešar and S. Špacapan, Broadcast domination of products of graphs, Ars Combin. 92 (2009) 303–320.
- R.C. Brewster, G. MacGillivray and F. Yang, Broadcast domination and multipacking in strongly chordal graphs, Discrete Appl. Math. 261 (2019) 108–118.
https://doi.org/10.1016/j.dam.2018.08.021 - R.C. Brewster, C.M. Mynhardt and L. Teshima, New bounds for the broadcast domination number of a graph, Open Math. 11 (2013) 1334–1343.
https://doi.org/10.2478/s11533-013-0234-8 - E.J. Cockayne, S. Herke and C.M. Mynhardt, Broadcasts and domination in trees, Discrete Math. 311 (2011) 1235–1246.
https://doi.org/10.1016/j.disc.2009.12.012 - J. Dabney, B.C. Dean, and S.T. Hedetniemi, A linear-time algorithm for broadcast domination in a tree, Networks 53 (2009) 160–169.
https://doi.org/10.1002/net.20275 - 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, 2001).
- D.J. Erwin, Dominating broadcasts in graphs, Bull. Inst. Combin. Appl. 42 (2004) 89–105.
- L. Gemmrich and C.M. Mynhardt, Broadcasts in graphs: Diametrical trees, Australas. J. Combin. 69 (2017) 243–258.
- B.L. Hartnell and C.M. Mynhardt, On the difference between broadcast and multipacking numbers of graphs, Util. Math. 94 (2014) 19–29.
- S.T. Hedetniemi, Unsolved algorithmic problems on trees, AKCE Int. J. Graphs Comb. 3 (2006) 1–37.
https://doi.org/10.1080/09728600.2006.12088803 - 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 - S. Herke and C.M. Mynhardt, Radial trees, Discrete Math. 309 (2009) 5950–5962.
https://doi.org/10.1016/j.disc.2009.04.024 - S. Lunney and C.M. Mynhardt, More trees with equal broadcast and domination numbers, Australas. J. Combin. 61 (2015) 251–272.
- 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. Teshima, Broadcasts and multipackings in trees, Util. Math. 104 (2017) 227–242.
- C.M. Mynhardt and J. Wodlinger, A class of trees with equal broadcast and domination numbers, Australas. J. Combin. 56 (2013) 3–22.
- C.M. Mynhardt and J. Wodlinger, Uniquely radial trees, J. Combin. Math. Combin. Comput. 93 (2015) 131–152.
- S.M. Seager, Dominating Broadcasts of Caterpillars, Ars Combin. 88 (2008) 307–319.
- K.W. Soh and K.M. Koh, Broadcast domination in graph products of paths, Australas. J. Combin. 59 (2014) 342–351.
Close