The total bondage number of grid graphs

Abstract

The total domination number of a graph $G$ without isolated vertices is the minimum number of vertices that dominate all vertices in $G$. The total bondage number $b_t(G)$ of $G$ is the minimum number of edges whose removal enlarges the total domination number. This paper considers grid graphs. An $(n,m)$-grid graph $G_{n,m}$ is defined as the cartesian product of two paths $P_n$ and $P_m$. This paper determines the exact values of $b_t(G_{n,2})$ and $b_t(G_{n,3})$, and establishes some upper bounds of $b_t(G_{n,4})$.

15 pages with 4 figures