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.
 A: 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.
