On (<i>t, r</i>) Broadcast Domination of Directed Graphs

Abstract

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.