Efficient k k -limited Dominating Broadcasts in Product Graphs
Bharadwaj, A.Senthil Thilak · 2025
Read Efficient k k -limited Dominating Broadcasts in Product Graphs by Bharadwaj, A.Senthil Thilak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-04087.txt.
Description
Senthil Thilak Bharadwaj published this graph theory paper in 2025. Domination is a classic graph topic: a set of vertices dominates a graph when every vertex is in the set or next to one in it. A broadcast generalizes this by giving each chosen vertex a strength, letting it dominate everything within that distance. The paper merges broadcasts with the demand of efficiency, meaning every vertex is dominated exactly once, never twice and never missed.
For such an efficient broadcast with strengths capped at k, the paper defines a number, mcr, as the smallest cap that works for a given graph. Bharadwaj proves that computing this number is NP-complete for general graphs, so no fast exact method is expected. The paper then works out the values and related measures for standard graph families and for product graphs built by combining simpler ones.
Catalog record
| CREATOR | Bharadwaj, A.Senthil Thilak |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 30 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-04087