Given natural numbers $n$ and $k$, let $G_{n,k}$ denote the simple graph whose vertex set is $\{1,2,\ldots ,n\}$ and there is an edge between $i$ and $j$ when $|i-j|\leq k$. I am interested in the independence number (size of the maximum independent set) of the graph $(G_{n,k})^{\Box d}$ (i.e. Cartesian product of $d$ copies of $G_{n.k}$). Are there any results known about such graphs? Even any results for small values of $d$ (e.g. $d=2,3$) would also be interesting to me.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ For $d=2$ and $n=(k+1)q+r$ you can easily partition the grid without $r\times r$ square by $(n^2-r^2)/(k+1)$ $1 \times (k+1)$ rectangles, and cover the remaining $r\times r$ square by $r$ such rectangles, this gives the upper bound $r+(n^2-r^2)/(k+1)$. It is achieved if you consider the points with prescribed sum of coordinates modulo $k+1$, the value of this remainder is choose so that the whole diagonal of the remaining $r\times r$ square is chosen $\endgroup$– Fedor PetrovCommented Jan 26, 2023 at 12:26
Add a comment
|