Results 1 to 4 of 4

Math Help - Graph Theory

  1. #1
    Newbie
    Joined
    Jul 2011
    Posts
    4

    Graph Theory

    Find the number of paths of length 'n' between any two vertices in K4 if the value of n is 4,5.


    (The problem belongs to Discrete Mathematics by Kenneth H Rosen, Sect 8.4 , problem no. 17)


    when the value of n is 2 or 3, it can be solved by observation.
    Is there a general formulae for the purpose ?

    Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Graph Theory

    You an use the property that powers of the adjacency matrix give the number of paths from one vertex to another. For paths of length 4, for example, we have 21 paths from a vertex to itself and 20 paths from one vertex to another.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2

    Re: Graph Theory

    If you want to find the general answer, then see if you can diagonalize the adjacency matrix. Then you can easily take arbitrary powers of the matrix.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jul 2011
    Posts
    4

    Re: Graph Theory

    thanks a ton..
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 05:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum