Broadcast domination in Tori

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


1 Dept of Mathematics, National University of Singapore

2 Department of Mathematics National University of Singapore


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}$‎.


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
Volume 4, Issue 4 - Serial Number 4
December 2015
Pages 43-53
  • Receive Date: 21 October 2014
  • Revise Date: 06 January 2015
  • Accept Date: 06 January 2015
  • Published Online: 01 December 2015