Tom Shlomi - Bounds On $(t,r)$ Broadcast Domination of $n$-Dimensional Grids

dmtcs:5732 - Discrete Mathematics & Theoretical Computer Science, April 3, 2023, vol. 24, no. 1 -
Bounds On $(t,r)$ Broadcast Domination of $n$-Dimensional GridsArticle

Authors: Tom Shlomi

    In this paper, we study a variant of graph domination known as $(t, r)$ broadcast domination, first defined in Blessing, Insko, Johnson, and Mauretour in 2015. In this variant, each broadcast provides $t-d$ reception to each vertex a distance $d < t$ from the broadcast. If $d \ge t$ then no reception is provided. A vertex is considered dominated if it receives $r$ total reception from all broadcasts. Our main results provide some upper and lower bounds on the density of a $(t, r)$ dominating pattern of an infinite grid, as well as methods of computing them. Also, when $r \ge 2$ we describe a family of counterexamples to a generalization of Vizing's Conjecture to $(t,r)$ broadcast domination.

    Volume: vol. 24, no. 1
    Section: Combinatorics
    Published on: April 3, 2023
    Accepted on: March 31, 2022
    Submitted on: August 30, 2019
    Keywords: Mathematics - Combinatorics,05C63, 05C69, 05C85

    Consultation statistics

    This page has been seen 301 times.
    This article's PDF has been downloaded 156 times.