Vertices pairwise in grid graph

**lambdacrash** · December 12th 2009, 04:09 AM

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 ?

**lambdacrash** · December 13th 2009, 07:41 AM

Hi !

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

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

$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 ?

PS: please excuse my bad english

Thread: Vertices pairwise in grid graph

LinkBack

Thread Tools

Display

Vertices pairwise in grid graph

Similar Math Help Forum Discussions

colouring vertices in graph theory

how many vertices does this graph have.....

Eulerian graph with even vertices and odd edges

Vertices of a simple graph

Explain why, in ANY graph, there must be an even number of odd vertices...

Search Tags