Results 1 to 3 of 3

Math Help - Graph Theory Problem

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    296

    Graph Theory Problem

    Is it possible to have a geodesic whose length is diam (G) for a graph G or is this a contradiction? A u-v geodesic is a u-v path of length d(u,v), but diam(G) is the greatest distance between any vertices of a connected graph G....So is it possible for me to have a geodesic with length diam(G)?

    More specifically the problem gives me a picture of a graph and asks me to find an example of a geodesic with length diam (G) or explain why none exist. The graph is like

    r-s-t
    | | |
    u-v-w
    | | |
    x-y-z

    Those are the 9 vertices and the lines are edges. Also, there is an edge between r and v and between t and v.

    Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,441
    Thanks
    1862
    Quote Originally Posted by zhupolongjoe View Post
    Is it possible to have a geodesic whose length is diam (G) for a graph G or is this a contradiction? A u-v geodesic is a u-v path of length d(u,v), but diam(G) is the greatest distance between any vertices of a connected graph G....So is it possible for me to have a geodesic with length diam(G)?

    More specifically the problem gives me a picture of a graph and asks me to find an example of a geodesic with length diam (G) or explain why none exist. The graph is like

    r-s-t
    | | |
    u-v-w
    | | |
    x-y-z

    Those are the 9 vertices and the lines are edges. Also, there is an edge between r and v and between t and v.

    Thank you.
    What is diam(G) for this graph? Can you find two points whose shortest path between them is equal to that?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    296
    Well diam(G) here would be 4. Because of the diagonals on the top, I can not find any two vertices like that. Each pair of vertices can be attained in a path of 3 or less. So does that mean that such does not exist?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 18th 2010, 09:36 PM
  2. graph theory problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 20th 2009, 08:50 PM
  3. Graph Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 9th 2009, 01:50 PM
  4. A graph theory problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 15th 2009, 12:08 PM
  5. Help with Graph Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 2nd 2008, 11:08 PM

Search Tags


/mathhelpforum @mathhelpforum