A dominating set of a graph G is a set of vertices that contains at least one endpoint of every edge on the graph. The domination number of G is the order of a minimum dominating set of G. The (t, r) broadcast domination is a generalization of domination in which a set of broadcasting vertices emits signals of strength t that decrease by 1 as they traverse each edge, and we require that every vertex in the graph receives a cumulative signal of at least r from its set of broadcasting neighbors. In this paper, we extend the study of (t, r) broadcast domination to directed graphs. Our main result explores the interval of values obtained by considering the directed (t, r) broadcast domination numbers of all orientations of a graph G. In particular, we prove that in the cases r = 1 and (t, r) = (2, 2), for every integer value in this interval, there exists an orientation of G which has directed (t, r) broadcast domination number equal to that value. We also investigate directed (t, r) broadcast domination on the finite grid graph, the star graph, the infinite grid graph, and the infinite triangular lattice graph. We conclude with some directions for future study.
References
[1]
Berge, C. (1962) Theory of Graphs and Its Applications. Methuen, London.
[2]
Ore, O. (1962) Theory of Graphs. American Mathematical Society Colloquium Publications, Providence, 38. https://doi.org/10.1090/coll/038
Haynes, T.W., Hedetniemi, S. and Slater, P. (1998) Fundamentals of Domination in Graphs. CRC Press, Boca Raton. https://doi.org/10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F
[5]
Henning, M.A., Oellermann, O.R. and Swart, H.C. (1991) Bounds on Distance Domination Parameters. Journal of Combinatorics, Information and System Sciences, 16, 11-18.
[6]
Farina, M. and Grez, A. (2016) New Upper Bounds on the Distance Domination Numbers of Grids. Rose-Hulman Undergraduate Mathematics Journal, 17, 133-145.
[7]
Drews, B.F., Harris, P.E. and Randolph, T.W. (2019) Optimal (t, r) Broadcasts on the Infinite Grid. Discrete Applied Mathematics, 255, 183-197. https://doi.org/10.1016/j.dam.2018.08.009
[8]
Hassan, M., Al Hassan, M. and Mostafa, M. (2020) The Signed Domination Number of Cartesian Product of Two Paths. Open Journal of Discrete Mathematics, 10, 45-55. https://doi.org/10.4236/ojdm.2020.102005
[9]
Blessing, D., Insko, E., Johnson, K. and Mauretour, C. (2015) On (t, r) Broadcast Domination Numbers of Grids. Discrete Applied Mathematics, 187, 19-40. https://doi.org/10.1016/j.dam.2015.02.005
[10]
Randolph, T.W. (2019) Asymptotically Optimal Bounds for (t, 2) Broadcast Domination on Finite Grids. Rose-Hulman Undergraduate Mathematics Journal, 20. https://scholar.rose-hulman.edu/rhumj/vol20/iss1/5
[11]
Herrman, R. and Hintum, P. (2021) The (t, r) Broadcast Domination Number of Some Regular Graphs. Discrete Applied Mathematics, 289, 270-280. https://doi.org/10.1016/j.dam.2020.11.014
[12]
Crepeau, N., Harris, P.E., Hays, S., Loving, M., Rennie, J., Rojas Kirby, G. and Vasquez, A. (2019) On (t, r) Broadcast Domination of Certain Grid Graphs.
[13]
Harris, P.E., Luque, D., Flores, C. and Sepulveda, N. (2020) Efficient (t, r) Broadcast Dominating Sets of the Triangular Lattice. Discrete Applied Mathematics, 277, 180-192. https://doi.org/10.1016/j.dam.2019.08.025
[14]
Harris, P.E., Insko, E. and Johnson, K. (2020) Projects in (t, r) Broadcast Domination. In: A Resourceful Guide to Undergraduate Research in Mathematics: Starting and Sustaining Accessible Undergraduate Research, Springer, Berlin, 235-262. https://doi.org/10.1007/978-3-030-37853-0_8
[15]
Chartrand, G. and Zhang, P. (2012) A First Course in Graph Theory. Dover Publications, Mineola.
[16]
Shang, Y. (2013) Large Dicliques in a Directed Inhomogeneous Random Graph. International Journal of Computer Mathematics, 90, 445-456. https://doi.org/10.1080/00207160.2012.735663
[17]
Berliner, A., Brown, C., Carlson, J., Cox, N., Hogben, L., Hu, J., Jacobs, K., Manternach, K., Peters, T., Warnberg, N. and Young, M. (2015) Path Cover Number, Maximum Nullity, and Zero Forcing Number of Oriented Graphs and Other Simple Digraphs. Involve, 8, 147-167. https://doi.org/10.2140/involve.2015.8.147
[18]
Hollander, P. (2021) Directed-t-r-Broadcast-Domination. GitHub, San Francisco. https://github.com/peterhollander/directed-t-r-broadcast-domination
![\"\"](\"Edit_34f76611-5e48-488e-bcb9-5b9022321196.png\")
of G which has directed (t, r) broadcast domination number equal to that value. We also investigate directed (t, r) broadcast domination on the finite grid graph, the star graph, the infinite grid graph, and the infinite triangular lattice graph. We conclude with some directions for future study.
