Let $G_{n,m}$ be the $n \times m$ grid graph, i.e. $G= P_n \Box P_m$, and $T_{n,m}$ the $n\times m$ torus grid graph, i.e. $G= C_n \Box C_m$, where $P_n$ and $C_n$ indicate the path graph of length $n$ and the cycle graph of length $n$, respectively. The independent domination number $i(G)$ is defined to be the minimum cardinality among all maximal independent sets of vertices of $G$.

Is there any explicit formula for $i(G_{n,m})$ and $i(T_{n,m})$? If not, is there a lower bound sharper than the one given by corresponding domination numbers $\gamma(G_{n,m})$ and $\gamma(T_{n,m})$? Or is there any asymptotic results for $i(G_{n,m})/mn$ and $i(T_{n,m})/mn$ as $m,n \to \infty$?


The independent domination number of grid graphs is known. You can find what you are looking for in the following paper.

S. Crevals and P.R.J. Ostergard, Independent domination of grids, Discrete Math. 338 (2015), 1379-1384.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.