# Thread: Vertices pairwise in grid graph

1. ## Vertices pairwise in grid graph

Hi !
Let Gr=(V,A) a complete symmetric directed a*b grid graph. Arcs are unweighted.
a and b are respectively the width and the height of Gr. I suppose that a>=b. |V| = a*b

I want to count the number of vertices pairwise which are at distance equal to L in the grid. L is at least equal to 1 and at most equal to a+b.

Any ideas ?

2. Hi !

I am looking for an exact formulation in a close form.

I have a first formulation for a*b grid :
$
n(a,b,l) = 2\sum_{i=max((l-b),0)}^{min(a,l)} \left[ ((b-(l-i))(a-i)) \right]
- a\times max(b-l,0) - b\times max(a-l,0)
$

$n(a,b,l)$ denotes the number of vertices pairwise at distance l, into a a*b grid.

This first formulation is exact but I am looking for another formulation without the "min" and "max" terms.

Any ideas ?