2018/04/20 by Pamela E. Harris, Dalia K. Luque, Harris, Pamela E. +5
Computer Science · #05C12 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.1804.07812
openalex publication_date 2018/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Blessing, Insko, Johnson and Mauretour gave a generalization of the\ndomination number of a graph G=(V,E) called the (t,r) broadcast domination\nnumber which depends on the positive integer parameters t and r. In this\nsetting, a vertex v \∈ V is a broadcast vertex of transmission strength t\nif it transmits a signal of strength t-d(u,v) to every vertex u \∈ V,\nwhere d(u,v) denotes the distance between vertices u and v and d(u,v)\n<t. Given a set of broadcast vertices S\⊆ V, the reception at vertex\nu is the sum of the transmissions from the broadcast vertices in S. The set\nS \⊆ V is called a (t,r) broadcast dominating set if every vertex u\n\∈ V has a reception strength r(u) \≥ r and for a finite graph G the\ncardinality of a smallest broadcast dominating set is called the (t,r)\nbroadcast domination number of G. In this paper, we consider the infinite\ntriangular grid graph and define efficient (t,r) broadcast dominating sets as\nthose broadcasts that minimize signal waste. Our main result constructs\nefficient (t,r) broadcasts on the infinite triangular lattice for all t\≥\nr\≥ 1. Using these broadcasts, we then provide upper bounds for the (t,r)\nbroadcast domination numbers for triangular matchstick graphs when\n(t,r)\∈ (2,1),(3,1),(3,2),(4,1),(4,2),(4,3),(t,t) .\n