Lower Bounds for the Exponential Domination Number of $C_m\times C_n$

Abstract

A vertex $v$ in a porous exponential dominating set assigns weight ${\left(\frac{1}{2}\right)}^{dist(v,u)}$ to vertex $u$. A porous exponential dominating set of a graph $G$ is a subset of $V(G)$ such that every vertex in $V(G)$ has been assigned a sum weight of at least 1. In this paper the porous exponential dominating number, denoted by ${\gamma }_e^{\ast }(G)$, for the graph $G=C_m\times C_n$ is discussed. Anderson et. al. proved that $\frac{mn}{15.875}\le {\gamma }_e^{\ast }(C_m\times C_n)\le \frac{mn}{13}$ and conjectured that $\frac{mn}{13}$ is also the asymptotic lower bound. We use a linear programing approach to sharpen the lower bound to $\frac{mn}{13.7619+\epsilon (m,n)}$.