Article in volume
Authors:
Jishnu Sen
National Institute of Technology Karnataka, Surathkal
Mangalore, Karnataka 575025
email: senjishnu5@gmail.com
Srinivasa Rao Kola
National Institute of Technology Karnataka, Surathkal
Mangalore, Karnataka 575025
email: srinu.iitkgp@gmail.com
Title:
Critical aspects in broadcast domination
PDFSource:
Discussiones Mathematicae Graph Theory 44(4) (2024) 1485-1512
Received: 2022-12-10 , Revised: 2023-06-22 , Accepted: 2023-06-24 , Available online: 2023-07-19 , https://doi.org/10.7151/dmgt.2506
Abstract:
A dominating broadcast labeling of a graph $G$ is a function $f : V(G)
\rightarrow \lbrace 0, 1, 2, \dots ,\text{diam}(G)\rbrace$ such that $f(v)
\leqslant e(v)$ for all $v \in V(G)$ and
$$
\bigcup_{\substack{v \in V(G)\\ {\small f(v) > 0}}} [\lbrace u \in V(G) : d(u,v)
\leqslant f(v) \rbrace]=V(G),
$$
where $e(v)$ is the eccentricity of $v$. The cost of $f$ is $\sum_{v \in V(G)}
f(v)$. The minimum of costs over all the dominating broadcast labelings of $G$
is called the broadcast domination number $\gamma_{b}(G)$ of $G$. In this paper,
we introduce the critical aspects in broadcast domination and study it with
respect to edge deletion and edge addition. A graph $G$ is said to be
$k$-$\gamma_{b}^{+}$-edge-critical ($k$-$\gamma_{b}^{-}$-edge-critical) if
$\gamma_{b}(G-e) > \gamma_{b}(G)$, for every edge $e \in E(G)$ (if
$\gamma_{b}(G+e) < \gamma_{b}(G)$, for every edge $e \notin E(G)$), where
$\gamma_{b}(G)=k$. We give a necessary and sufficient condition for a graph to
be $k$-$\gamma_{b}^{+}$-edge-critical. We characterize
$k$-$\gamma_{b}^{-}$-edge-critical graphs for $k=1, 2$, and give necessary
conditions of the same for $k \geqslant 3$. Further, we define the broadcast
bondage number and the broadcast reinforcement number of a graph, and give tight
upper bounds for them.
Keywords:
dominating broadcast labeling, broadcast domination number, critical graph, bondage number, reinforcement number
References:
- D. Bauer, F. Harary, J. Nieminen and C.L. Suffel, Domination alteration sets in graphs, Discrete Math. 47 (1983) 153–161.
https://doi.org/10.1016/0012-365X(83)90085-7 - B. Brešar and S. Špacapan, Broadcast domination of products of graphs, Ars Combin. 92 (2009) 303–320.
- 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.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, Ph.D. Thesis (Department of Mathematics and Statistics, Western Michigan University, 2001).
- O. Favaron, D.P. Sumner and E. Wojcicka, The diameter of domination k-critical graphs, J. Graph Theory 18 (1994) 723–734.
https://doi.org/10.1002/jgt.3190180708 - J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, The bondage number of a graph, Discrete Math. 86 (1990) 47–57.
https://doi.org/10.1016/0012-365X(90)90348-L - B.L. Hartnell and D.F. Rall, A characterization of trees in which no edge is essential to the domination number, Ars Combin. 33 (1992) 65–76.
- B.L. Hartnell and D.F. Rall, Bounds on the bondage number of a graph, Discrete Math. 128 (1994) 173–177.
https://doi.org/10.1016/0012-365X(94)90111-2 - T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Boca Raton, CRC Press, 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 - S. Herke, Dominating Broadcasts in Graphs, Master's Thesis (Department of Mathematics and Statistics, University of Victoria, 2009).
- S. Herke and C.M. Mynhardt, Radial trees, Discrete Math. 309 (2009) 5950–5962.
https://doi.org/10.1016/j.disc.2009.04.024 - J. Kok and C.M. Mynhardt, Reinforcement in graphs, Congr. Numer. 79 (1990) 225–231.
- C.L. Liu, Introduction to Combinatorial Mathematics (McGraw-Hill, 1968).
- 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.
- V. Samodivkin, The bondage number of graphs: good and bad vertices, Discuss. Math. Graph Theory 28 (2008) 453–462.
https://doi.org/10.7151/dmgt.1419 - S.M. Seager, Dominating broadcasts of caterpillars, Ars Combin. 88 (2008) 307–319.
- D.P. Sumner and P. Blitch, Domination critical graphs, J. Combin. Theory. Ser. B 34 (1983) 65–76.
https://doi.org/10.1016/0095-8956(83)90007-2 - U. Teschner, A new upper bound for the bondage number of graphs with small domination number, Australas. J. Combin. 12 (1995) 27–36.
- U. Teschner, New results about the bondage number of a graph, Discrete Math. 171 (1997) 249–259.
https://doi.org/10.1016/S0012-365X(96)00007-6 - H.B. Walikar and B.D. Acharya, Domination critical graphs, Nat. Acad. Sci. Lett. 2(2) (1979) 70–72.
- Y.-L.Wang, On the bondage number of a graph, Discrete Math. 159 (1996) 291–294.
https://doi.org/10.1016/0012-365X(96)00347-0 - E. Wojcicka, Hamiltonian properties of domination-critical graphs, J. Graph Theory 14 (1990) 205–215.
https://doi.org/10.1002/jgt.3190140209
Close