Paths in K[m,n]

[e(ho0n3]

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 n^j/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

- n^j/2(m - 1)^{j/2 - 1} if v[0] = v[j]

- n^j/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

- m^j/2(n - 1)^{j/2 - 1} if v[0] = v[j]

- m^j/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?

[haggy]

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.

[e(ho0n3]

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

[fuhrerkeebs]

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.

[fuhrerkeebs]

In case you don't know what the adjacency matrix is...http://mathworld.wolfram.com/AdjacencyMatrix.html

[e(ho0n3]

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 A^j.

[e(ho0n3]

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 n^j/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 m^{j/2 - 1} ways. The answer then is n^j/2m^{j/2 - 1}.

 

Question 2 is similar to question 1 (except M and N are reversed), so the answer is m^j/2n^{j/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).

[e(ho0n3]

I've attached a proof for all those interested.

paths.pdf