Jump to content
Sign in to follow this  
e(ho0n3

Paths in K[m,n]

Recommended Posts

Let K[m,n] be a complete bipartite graph and let M and N be the set of vertices with |M| = m and |N| = n such that every edge is incident on one vertex in M and one vertex in N.

 

I have three questions:

1. If v and w are in M, how many paths are there from v to w of length j?

2. If v and w are in N, how many paths are there from v to w of length j?

3. If v is in M and w is in N, how many paths are there from v to w of length j?

 

For questions 1 and 2, if j is odd, the answer is 0. For question 3, if j is even, the answer is also 0. (I can prove this if anybody is interested).

 

For question 1, assume j is even and let P = (v[0], v[1], v[2], ..., v[j]) be a path from v = v[0] to w = v[j]. Notice that vertices with an odd-numbered index belong to N and those with an even-numbered index belong to M. How many odd-numbered index vertices are there? Easy, j/2. Once can choose j/2 vertices from N for the path P in nj/2 ways. How many even-numbered index vertices are there in P, excluding v[0] and v[j]? Easy, j/2 - 1. If v[0] = v[j], one can pick j/2 - 1 vertices from M for the path P in (m - 1)j/2 - 1 ways. If v[0] ≠ v[j], one can pick j/2 - 1 vertices from M for the path P in (m - 2)j/2 - 1 ways. So the answer to question 1 is

- nj/2(m - 1)j/2 - 1 if v[0] = v[j]

- nj/2(m - 2)j/2 - 1 if v[0] ≠ v[j]

 

 

Question 2 is similar to question 1 (except M and N are reversed), so the answer is

- mj/2(n - 1)j/2 - 1 if v[0] = v[j]

- mj/2(n - 2)j/2 - 1 if v[0] ≠ v[j]

 

For question 3, assume j is odd and let P = (v[0], v[1], v[2], ..., v[j]) be a path from v = v[0] to w = v[j]. Notice that vertices with an odd-numbered index belong to N and those with an even-numbered index belong to M. There are (j + 1)/2 - 1 vertices having even index, excluding v[0]. There are also (j + 1)/2 - 1 vertices having odd index, excluding v[j]. Hence, the answer to the question is ((m - 1)(n - 1))(j + 1)/2 - 1.

 

Am I correct here?

Share this post


Link to post
Share on other sites

I haven't looked at this closely but you need to consider repetition of vertices. A path is a walk that has no vertices repeated.

 

I think your working will change to something like n "choose" j/2 etc.

Share this post


Link to post
Share on other sites

According to my book, a path can have repeated vertices. A path with no repeated vertices is called a simple path.

Share this post


Link to post
Share on other sites

Well if you can repeat vertices, then you can just find the corresponding adjacency matrix of the graph, raise it to the jth power, and if you look at the intersection of the two vertices in the matrix, it will tell you the number of paths between the two vertices that are of length j.

Share this post


Link to post
Share on other sites

I know what an adjancency matrix is. Actually, I asked this question because I need to derive the jth power adjencency matrix of K[m,n]. In other words, if A is the adjencency matrix of K[m,n], derive a formula for the members of Aj.

Share this post


Link to post
Share on other sites

Thanks to a colleague of mine, I'm now aware of an error in my solution. Basically I didn't consider the repetition of the start and end vertices in the path. So...

 

For question 1, assume j is even and let P = (v[0], v[1], v[2], ..., v[j]) be a path from v = v[0] to w = v[j]. Notice that vertices with an odd-numbered index belong to N and those with an even-numbered index belong to M. How many odd-numbered index vertices are there? Easy, j/2. Once can choose j/2 vertices from N for the path P in nj/2 ways. How many even-numbered index vertices are there in P, excluding v[0] and v[j]? Easy, j/2 - 1. One can pick j/2 - 1 vertices from M for the path P in mj/2 - 1 ways. The answer then is nj/2mj/2 - 1.

 

Question 2 is similar to question 1 (except M and N are reversed), so the answer is mj/2nj/2 - 1.

 

For question 3, assume j is odd and let P = (v[0], v[1], v[2], ..., v[j]) be a path from v = v[0] to w = v[j]. Notice that vertices with an odd-numbered index belong to N and those with an even-numbered index belong to M. There are (j + 1)/2 - 1 vertices having even index, excluding v[0]. There are also (j + 1)/2 - 1 vertices having odd index, excluding v[j]. Hence, the answer to the question is (mn)(j + 1)/2 - 1.

 

I'll post a proof by induction that my solution is correct later (if it is correct that is).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.