The square grid graph is defined as the graph $G = ([m] \times [n], E)$ for integers $m,n$, such that for $x_1, x_2 \in [m], y_1, y_2\in [n]$, $(x_1,y_1)$ is adjacent to $(x_2,y_2)$ if and only if $x_1 = x_2, |y_1 - y_2| = 1$ or $y_1 = y_2, |x_1 - x_2| = 1$. In other words, it is the king graph without diagonal edges.

I am interested in finding a way to enumerate all of the connected subgraphs of $G$. I am somewhat at a loss for how to even approach this question. My only idea is to try to find some kind of recursive relationship based on $m$ and $n$; if I know what all of the connected subgraphs of $H = ([m-1] \times [n-1], E)$ are, then perhaps I can count the number of ways to attach some number of vertices and edges from the outer row and column to the already existent subgraphs of $H$ in order to form connected subgraphs of $G$, but this would require knowing exactly how many subgraphs of $H$ are adjacent to each specific vertex in the outer row and column of $G$. I feel like such a calculation would get very messy even for small numbers.

I'm curious if there are any techniques that would make this counting easier. I'm also curious if there are any techniques just for counting paths on $G$. Any suggestions or hints would be appreciate. Thank you.

  • $\begingroup$ I'm afraid that, on the problem of counting connected subgraphs, you're right. (Try to obtain recurrences for small fixed $m$, say.) Regarding counting paths - this must be much easier. $\endgroup$ – metamorphy Sep 12 '18 at 16:09

I believe your question is a bit hard to answer, put notice that your question is equivalent to the following: let us define $R_k$ as the number of ways to remove k vertices from the $m\times n$ grid so that the "new" created subgraph is connected, then the number of connected subgraphs is $\sum_{k=0}^{n^2}R_k$. now we see that the major problem in evaluating $R_k$ is calculating how many islands you can make, since islands make the "new" subgraph disconnected (i believe you understand my meaning in "islands"). The number of islands with k vertices is the number of k Poly-kings (see https://en.wikipedia.org/wiki/Pseudo-polyomino) for which I'm afraid there is no closed formula as far as i know. after all counting how many islands you can make by "deleting" k vertices is basically the number of k poly-kings

i hope that satisfy you for now...


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.