top of page

Broadcast domination on triangular grid graphs

Updated: May 7, 2018

A recently submitted article with Dalia Luque, Claudia Reyes, and Nohemi Sepulveda, three Williams College graduating seniors.


Blessing, Insko, Johnson and Mauretour gave a generalization of the domination number of a graph G = (V, E) called the (t, r) broadcast domination number which depends on the positive integer parameters t and r. In this setting, a vertex v ∈ V is a broadcast vertex of transmission strength t if it transmits a signal of strength t−d(u, v) to every vertexu ∈ V , where d(u, v) denotes the distance between vertices u and v and d(u, v) < t. Given a set of broadcast vertices S ⊆ V , the reception at vertex u is the sum of the transmissions from the broadcast vertices in S. The set S ⊆ V is called a (t, r) broadcast dominating set if every vertex u ∈ V has a reception strength r(u) ≥ r and for a finite graph G the cardinality of a smallest broadcast dominating set is called the (t, r) broadcast domination number ofG. In this paper, we consider the infinite triangular grid graph and define efficient (t,r) broadcast dominating sets as those broadcasts that minimize signal waste. Our main result constructs efficient (t, r) broadcasts on the infinite triangular lattice for all t ≥ r ≥ 1. Using these broadcasts, we then provide upper bounds for the (t, r) broadcast domination numbers for triangular matchstick graphs when (t, r) ∈ {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3), (t, t)}.

87 views0 comments

Recent Posts

See All

My questions for guiding an initial mentoring meeting

By Pamela E. Harris In my new position as a professor at a research institution, I am beginning to build mentor-mentee relationships with graduate students, which (as is expected) are relationships th


bottom of page