Broadcast domination in Tori

Document Type: 75th Birthday of G. B. Khosrovshahi

Authors

1 Dept of Mathematics, National University of Singapore

2 Department of Mathematics National University of Singapore

Abstract

A broadcast on a graph $G$ is a function $f‎ : ‎V(G) \rightarrow \{0‎, ‎1,\dots‎, ‎diam(G)\}$ such that for every vertex $v \in V(G)$‎, ‎$f(v) \leq e(v)$‎, ‎where $diam(G)$ is the diameter of $G$‎, ‎and $e(v)$ is the eccentricity of $v$‎. ‎In addition‎, ‎if every vertex hears the broadcast‎, ‎then the broadcast is a dominating broadcast. ‎The cost of a broadcast $f$ is the value $\sigma(f) = \sum_{v \in V(G)} f(v)$‎. ‎In this paper we determine the minimum cost of a dominating broadcast (also known as the broadcast domination number) for a torus $C_{m} \;\Box\; C_{n}$‎.

Keywords

Main Subjects


D‎. ‎Erwin (2004). ‎Dominating broadcasts in graph. Bull‎. ‎Inst‎. ‎Comb‎. ‎Appl.. 42, 89-105
J‎. ‎Dunbar‎, ‎D‎. ‎Erwin‎, ‎T‎. ‎Haynes‎, ‎S‎. ‎M‎. ‎Hedetniemi ‎and‎ ‎S‎. ‎T‎. ‎Hedetniemi (2006). ‎Broadcasts in graphs. Discrete Appl‎. ‎Math.. 154, 59-75