On (t,r) broadcast domination of certain grid graphs

Crepeau, Natasha; Harris, Pamela E.; Hays, Sean; Loving, Marissa; Rennie, Joseph; Rojas Kirby, Gordon; Vasquez, Alexandro

doi:10.2140/involve.2023.16.883

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

On $(t,r)$ broadcast domination of certain grid graphs

Natasha Crepeau, Pamela E. Harris, Sean Hays, Marissa Loving, Joseph Rennie, Gordon Rojas Kirby and Alexandro Vasquez

Vol. 16 (2023), No. 5, 883–903

DOI: 10.2140/involve.2023.16.883

Abstract

Let $G = (V (G), E (G))$ be a connected graph with vertex set $V (G)$ and edge set $E (G)$ . We say a subset $D$ of $V (G)$ dominates $G$ if every vertex in $V ∖ D$ is adjacent to a vertex in $D$ . A generalization of this concept is $(t, r)$ broadcast domination. We designate certain vertices to be towers of signal strength $t$ , which send out signal to neighboring vertices with signal strength decaying linearly as the signal traverses the edges of the graph. We let $𝕋$ be the set of all towers, and we define the signal received by a vertex $v \in V (G)$ from all towers $w \in 𝕋$ to be $f (v) = \sum_{w \in 𝕋} \max (0, t - d (v, w))$ . Blessing, Insko, Johnson and Mauretour defined a $(t, r)$ broadcast dominating set, or a $(t, r)$ broadcast, on $G$ as a set $𝕋 \subseteq V (G)$ such that $f (v) \geq r$ for all $v \in V (G)$ . The minimum cardinality of a $(t, r)$ broadcast on $G$ is called the $(t, r)$ broadcast domination number of $G$ . We present our research on the $(t, r)$ broadcast domination number for certain graphs including paths, grid graphs, the slant lattice, and the king’s lattice.

Keywords

graph domination, grid graphs

Mathematical Subject Classification

Primary: 05C12, 05C30, 05C69

Milestones

Received: 23 August 2022

Accepted: 1 December 2022

Published: 9 December 2023

Communicated by Joel Foisy

Authors

Natasha Crepeau
Department of Mathematics University of Washington Seattle, WA United States

Pamela E. Harris
Department of Mathematical Sciences University of Wisconsin-Milwaukee Milwaukee, WI United States

Sean Hays
Department of Mathematics The University of Alabama Tuscaloosa, AL United States

Marissa Loving
Department of Mathematics University of Wisconsin-Madison Madison, WI United States

Joseph Rennie
Department of Mathematics University of Illinois at Urbana-Champaign Urbana, IL United States

Gordon Rojas Kirby
School of Mathematics and Statistical Sciences Arizona State University Tempe, AZ United States

Alexandro Vasquez
Department of Mathematics Manhattan College Riverdale, NY 10471 United States

Vol. 16, No. 5, 2023