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

CREATORBharadwaj, A.Senthil Thilak
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE30 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-04087

Browse the full library · About the Tower of Babel