5
$\begingroup$

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$?

$\endgroup$
1

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .