# Number of nodes within distance $t$ from a specific node $v$ on a grid graph

Given an undirected grid graph $$G$$, a node $$v$$ and an integer $$t$$, is there a way to give an upper bound for the number of nodes at distance exactly $$t$$ from $$v$$?

In addition, if we are given a second node in the graph $$u$$, such that $$\mathrm{dist}(v,u)=C$$, can we give an upper bound on the number of nodes at distance $$t$$ from $$v$$ and $$C-t$$ from $$u$$ (all nodes in the $$t$$'th layer between them)?

The question refers to grid graphs, but if there is a way to approximate such bound for a general $$d$$-regular graph it will be helpful for my application as well.

By grid graph, do you mean the $$2$$-dimensional grid? If so, then the number of nodes $$t$$ away is just the number of vectors $$(a,b)$$ with $$|a|+|b|=t$$. If you fix the signs so $$a$$ and $$b$$ are non-negative, there are $$t+1$$ choices. You can have four combinations of signs, but this overcounts the four possibilities where one coordinate is $$0$$, so the exact answer is $$4(t+1)-4=4t$$.

You can do something similar in higher dimensions. In $$n$$ dimensions, an upper bound is $$2^n\binom{n+t-1}{t}$$ since there are $$2^n$$ ways to choose the signs and $$\binom{n+t-1}{t}$$ tuples of nonnegative integers summing to $$t$$, by stars and bars. Again, this overcounts some cases where some coordinates are $$0$$; you could in principle deal with this but it would make the bound more complicated and the above is roughly best possible for large $$t$$.

For general $$d$$-regular graphs, the answer is very different. You have to tak $$t$$ steps from your starting node, and at each step except the first you have $$d-1$$ choices (you can go in any direction except the one you just came from). It is possible for all of these $$d(d-1)^{t-1}$$ routes to give different vertices, and all of the vertices to be at distance exactly $$t$$ from the start (if your graph is the infinite $$d$$-regular tree), so you can't get a better general bound.

For the second question (nodes at distance $$t$$ from one and $$C-t$$ from the other), let's suppose without loss of generality that the first node is $$(0,...,0)$$ and the second node is $$(a_1,a_2,...,a_n)$$ with each $$a_i\geq 0$$, and that $$t\leq C-t$$ (otherwise swap the nodes round and you get a better bound). Then any node satisfying the conditions is $$(b_1,b_2,...,b_n)$$ with $$\sum_ib_i=t$$ and $$0\leq b_i\leq a_i$$ for each $$i$$. This is difficult to bound exactly, but a reasonable upper bound is to forget about the fact that $$b_i\leq a_i$$ and just take the number of possible tuples of $$b_i\geq 0$$ summing to $$t$$ which is $$\binom{n+t-1}{t}$$. This is smaller than the one-distance bound above by a factor of $$2^n$$; this is the best possible factor which is independent of $$C,t$$ but if these are small and $$n>2$$ then you could improve it slightly.

Again, that is only for grid graphs. In general for $$d$$-regular graphs you can't do better than $$d(d-1)^{t-1}$$ (the same bound as if you only know one distance), since the graph could look like a tree for the first $$t$$ layers.

• Thanks for the informed answer. Regarding the second question, why are the nodes represented by vector with $n$ entries? Is this the proper representation for a 2D grid graph? Or is it for the case of an $n$-dimensional grid? (What does $n$ represent here?) I was referring to a 2D grid only (sorry if that wasn't clear). Aug 25 '20 at 9:25
• In addition, what if we would like to answer the same question where $C$ is not the distance between $u$ and $v$, but a given value larger than dist($u$,$v$)? i.e. we want to count the number of nodes in distance $t$ from $u$ and $C-t$ from $v$, regardless the distance between them. Aug 25 '20 at 9:38
• @OfirGordon yes, $n$ was the dimension. If $n=2$ then this bound is actually best possible: if the two nodes are at opposite corners of a square of side $C/2$ and $t\leq C/2$ it is exact. Aug 25 '20 at 10:49
• For the extra question, it is now possible that $2t+1$ of the $4t$ nodes at distance $t$ from the first node are distance $C-t$ from the second. The case where this happens is e.g. when the two points are at $(0,0)$ and $(0,1)$ and $C-t=t+1$. Aug 25 '20 at 10:54
• You can't have more than this: the sets of nodes fulfilling each condition individually are diagonally-aligned squares, and two such squares can't meet on three sides unless they are the same (which would mean your two nodes are equal). Aug 25 '20 at 10:56