Results 1 to 2 of 2

Math Help - Vertices pairwise in grid graph

  1. #1
    Newbie
    Joined
    Dec 2009
    Posts
    2

    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 ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Dec 2009
    Posts
    2

    Angry

    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. colouring vertices in graph theory
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: December 3rd 2009, 04:53 PM
  2. how many vertices does this graph have.....
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 27th 2008, 07:30 PM
  3. Eulerian graph with even vertices and odd edges
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 23rd 2007, 04:12 PM
  4. Vertices of a simple graph
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 8th 2007, 04:37 PM
  5. Replies: 5
    Last Post: January 14th 2007, 03:55 PM

Search Tags


/mathhelpforum @mathhelpforum