Results 1 to 2 of 2

Math Help - Graph Theory

  1. #1
    Newbie
    Joined
    Apr 2008
    Posts
    4

    Graph Theory

    I'm stuck with the following problem.. any ideas?

    Find the number of walks of length n between two different, predetermined vertices in
    K4 if n is:
    i) 2
    ii) 3
    iii) 4
    iv) 5
    Define a recurrence relation for pn where pn is the number of walks of
    length n between two different, predetermined vertices in K4.


    I got that for n=2, there are two walks, for n=3 there are 5 paths, for n=4 there are 12....

    Are these right? Can you help me get the recurrence relation?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,790
    Thanks
    1687
    Awards
    1
    The adjacency matrix for K_4 is A_{K_4 }  = \left( {\begin{array}{cccc}   0 & 1 & 1 & 1  \\   1 & 0 & 1 & 1  \\   1 & 1 & 0 & 1  \\   1 & 1 & 1 & 0  \\\end{array}} \right).
    The third power is \left( {A_{K_4 } } \right)^3  = \left( {\begin{array}{cccc}<br />
   6 & 7 & 7 & 7  \\   7 & 6 & 7 & 7  \\   7 & 7 & 6 & 7  \\   7 & 7 & 7 & 6  \\ \end{array}} \right).

    So it appears the your calculation for n=3 is two off.
    If you square the matrix, you will see that you are correct for n=2.

    Suppose that S_n denotes the number of paths of length n from a vertex to itself. Clearly S_2 = 3 because each point is adjacent to three other vertices. Here is an example: ABA, ACA, & ADA.

    Suppose that T_n denotes the number of paths of length n between two vertices.
    Consider the two vertices D & B in the graph. If we want to know the number of paths of length (n+1) from D to B, then we must go through vertex A or C. So we can use any one of the T_n paths from D to A of length n and add AB to any one. We have the same idea using vertex C. But we can also go directly to B from D by using any path from D to D of length n.
    Thus we get T_{n+1}= 2T_n + S_n

    Now we need to find S_n in terms of T_{n-1}.
    Any path from D to D of length n has the last edge AD, BD, or CD.
    So count the number of the number of paths of length n-1 between two vertices.
    Thus we have S_{n}= 3T_{n-1} or T_{n+1}= 2T_n + 3T_{n-1}.
    Attached Thumbnails Attached Thumbnails Graph Theory-k4.gif  
    Last edited by Plato; May 16th 2008 at 03:07 PM.
    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