Open Journal of Discrete Mathematics

Volume 12, Issue 3 (July 2022)

ISSN Print: 2161-7635   ISSN Online: 2161-7643

Google-based Impact Factor: 0.64  Citations  

On (t, r) Broadcast Domination of Directed Graphs

HTML  XML Download Download as PDF (Size: 5270KB)  PP. 78-100  
DOI: 10.4236/ojdm.2022.123006    119 Downloads   688 Views  

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.

Share and Cite:

Harris, P. , Hollander, P. and Insko, E. (2022) On (t, r) Broadcast Domination of Directed Graphs. Open Journal of Discrete Mathematics, 12, 78-100. doi: 10.4236/ojdm.2022.123006.

Cited by

No relevant information.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.