Geodesic
Critical aspects in broadcast domination
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1485-1512 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A dominating broadcast labeling of a graph G is a function f : V(G) → 0, 1, 2, ...,diam(G) such that f(v) ≤ e(v) for all v ∈ V(G) and ⋃_v ∈ V(G) f(v) gt; 0 [ u ∈ V(G) : d(u,v) ≤ f(v) ]=V(G), where e(v) is the eccentricity of v. The cost of f is ∑_v ∈ V(G) f(v). The minimum of costs over all the dominating broadcast labelings of G is called the broadcast domination number γ_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-γ_b^+-edge-critical (k-γ_b^--edge-critical) if γ_b(G-e) gt; γ_b(G), for every edge e ∈ E(G) (if γ_b(G+e) lt; γ_b(G), for every edge e ∉ E(G)), where γ_b(G)=k. We give a necessary and sufficient condition for a graph to be k-γ_b^+-edge-critical. We characterize k-γ_b^--edge-critical graphs for k=1, 2, and give necessary conditions of the same for k ⩾ 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 
@article{DMGT_2024_44_4_a13,
     author = {Sen, Jishnu and Kola, Srinivasa Rao},
     title = {Critical aspects in broadcast domination},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1485--1512},
     year = {2024},
     volume = {44},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a13/}
}
TY  - JOUR
AU  - Sen, Jishnu
AU  - Kola, Srinivasa Rao
TI  - Critical aspects in broadcast domination
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1485
EP  - 1512
VL  - 44
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a13/
LA  - en
ID  - DMGT_2024_44_4_a13
ER  - 
%0 Journal Article
%A Sen, Jishnu
%A Kola, Srinivasa Rao
%T Critical aspects in broadcast domination
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1485-1512
%V 44
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a13/
%G en
%F DMGT_2024_44_4_a13
Sen, Jishnu; Kola, Srinivasa Rao. Critical aspects in broadcast domination. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1485-1512. http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a13/

[1] 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

[2] B. Brešar and S. Špacapan, Broadcast domination of products of graphs, Ars Combin. 92 (2009) 303–320.

[3] 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

[4] 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

[5] D.J. Erwin, Cost Domination in Graphs, Ph.D. Thesis (Department of Mathematics and Statistics, Western Michigan University, 2001).

[6] 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

[7] 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

[8] 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.

[9] 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

[10] 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

[11] 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

[12] S. Herke, Dominating Broadcasts in Graphs, Master's Thesis (Department of Mathematics and Statistics, University of Victoria, 2009).

[13] S. Herke and C.M. Mynhardt, Radial trees, Discrete Math. 309 (2009) 5950–5962. https://doi.org/10.1016/j.disc.2009.04.024

[14] J. Kok and C.M. Mynhardt, Reinforcement in graphs, Congr. Numer. 79 (1990) 225–231.

[15] C.L. Liu, Introduction to Combinatorial Mathematics (McGraw-Hill, 1968).

[16] C.M. Mynhardt and J. Wodlinger, A class of trees with equal broadcast and domination numbers, Australas. J. Combin. 56 (2013) 3–22.

[17] C.M. Mynhardt and J. Wodlinger, Uniquely radial trees, J. Combin. Math. Combin. Comput. 93 (2015) 131–152.

[18] 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

[19] S.M. Seager, Dominating broadcasts of caterpillars, Ars Combin. 88 (2008) 307–319.

[20] 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

[21] U. Teschner, A new upper bound for the bondage number of graphs with small domination number, Australas. J. Combin. 12 (1995) 27–36.

[22] 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

[23] H.B. Walikar and B.D. Acharya, Domination critical graphs, Nat. Acad. Sci. Lett. 2(2) (1979) 70–72.

[24] 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

[25] E. Wojcicka, Hamiltonian properties of domination-critical graphs, J. Graph Theory 14 (1990) 205–215. https://doi.org/10.1002/jgt.3190140209