2025/10/02 by Imran Allie, Allie, Imran, Brandon du Preez +4
Computer Science · Engineering · Medicine · #Advanced MIMO Systems Optimization #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Mathematics #Mathematical and Theoretical Epidemiology and Ecology Models
paper · pdf · doi:10.48550/arxiv.2510.02211
openalex publication_date 2025/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph and let S ⊆ V(G). It is said that S dominates N[S]. We say that S monitors vertices of G as follows. Initially, all dominated vertices are monitored. This step is called the domination step. Thereafter, the set of unmonitored vertices of which each is the only unmonitored neighbour of a monitored vertex, is monitored. This step is called a propagation step and is repeated until the process terminates. The process terminates when the there are no monitored vertices which have exactly one unmonitored neighbour. This combined process of initial domination and subsequent propagation is called power domination. If all vertices of G are monitored at termination, then S is said to be a power dominating set (PDS) of G. The power domination number of G, denoted as γp(G), is the minimum cardinality of a PDS of G. The propagation radius of G is the minimum number of steps it takes a minimum PDS to monitor V(G). In this paper we determine an upper bound on the propagation radius of G with regards to power domination, in terms of δ and n. We show that this bound is only attained when γp(G)=1 and then improve this bound for γp(G)≥ 2. Sharpness examples for these bounds are provided. We also present sharp upper bounds on the propagation radius of split graphs. We present sharpness results for a known lower bound of the propagation radius for all Δ≥ 3.