1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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). $\endgroup$ Aug 25 '20 at 9:25
  • $\begingroup$ 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. $\endgroup$ Aug 25 '20 at 9:38
  • $\begingroup$ @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. $\endgroup$ Aug 25 '20 at 10:49
  • $\begingroup$ 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$. $\endgroup$ Aug 25 '20 at 10:54
  • $\begingroup$ 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). $\endgroup$ Aug 25 '20 at 10:56

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.