image
Graph Theory Lessons

rule

previous index next Lesson 12: Paths of Length p in Kn


We have looked at powers of adjacency matrices and how they relate to paths in the graph. We now look specifically at the complete graphs and powers of their adjacency matrices.

Java Web Start Activity:
Run the Java Web Start application below again but this time concentrate on complete graphs Kn. Observe the values of the entries on the leading diagonal and those that are not on the leading diagonal.

Java Web Start Application 12.1: Paths of length n

We know that the adjacency matrix A of Kn has zeros on the leading diagonal and ones off the leading diagonal. By looking at a few examples you will see that the pattern seems to be that the entries on the leading diagonal of Ap have the same value (we shall call this value dp and the ones off the leading diagonal all have another common value which we shall call ep, different from dp.

Consider K3: Draw the graph K3 and by clicking the + button look at Ap, p=1, 2, ..., 5. Make a table like the one below.

table for n=3
Fig 12.1. n=3

Make similar tables for n=4, 5, and 6.

Questions:
  1. From your observations, when n=3,
    • what do you think is the relationship between d p+1 and e p?
    • what do you think is the relationship between d p and e p?
  2. Answer the question above for n=4, 5, and 6.
  3. Prove by induction that your answers to the above questions continue to hold for all values of n and p. Start your proof as follows:
    first part of proof
    Fig 12.2. First part of proof
    and try to get to the conclusion
    middle part of proof
    Fig 12.3. Middle part of proof
    Now work with those equations to get
    conclusion part of proof
    Fig 12.3. End of proof
  4. Check that the results of your proof above match what you had in your tables if you set n=3, 4, 5, and 6.
  5. You are asked to create a language for some hikers to use to signal messages to one another at night. The hikers will use colored flash lights to send the messages. They will have three colors, red blue and yellow. They should not flash the same color twice in a row because it could be mistaken for a flicker of the flashlight. Words in your language are five flashes long. That way the viewer knows that every five flashes are a word. To make it unlikely that the receiver loses track of where words begin and end you will have a long pause between words and will always start with a red flash and end with a yellow flash. So for instance red blue red blue yellow (written rbrby) would be a valid word but red red blue blue yellow (rrbby) would not.
    • How many words are there in your language? List all of them. [Hint: you will find it easier to list them in lexicographical order]
    • How would you change the rules if you wanted a vocabulary of 6 words? List the six words under your new rules.
    • How would you change the rules to get a vocabulary of 11 words? List the eleven words under you new rules.

Answers


© C. Mawata