Results 1 to 2 of 2

Thread: 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
    21,782
    Thanks
    2824
    Awards
    1
    The adjacency matrix for $\displaystyle K_4$ is $\displaystyle 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 $\displaystyle \left( {A_{K_4 } } \right)^3 = \left( {\begin{array}{cccc}
    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 $\displaystyle n=3$ is two off.
    If you square the matrix, you will see that you are correct for $\displaystyle n=2$.

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

    Suppose that $\displaystyle 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 $\displaystyle 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 $\displaystyle T_{n+1}= 2T_n + S_n$

    Now we need to find $\displaystyle S_n$ in terms of $\displaystyle 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 $\displaystyle S_{n}= 3T_{n-1}$ or $\displaystyle 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: Mar 10th 2012, 05:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 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: Aug 1st 2011, 03:30 AM
  4. Replies: 0
    Last Post: Sep 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jul 25th 2010, 11:15 PM

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum