## 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, v, v, ..., v[j]) be a path from v = v 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 and v[j]? Easy, j/2 - 1. If v = v[j], one can pick j/2 - 1 vertices from M for the path P in (m - 1)j/2 - 1 ways. If v ≠ 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 = v[j]

- nj/2(m - 2)j/2 - 1 if v ≠ 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 = v[j]

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

For question 3, assume j is odd and let P = (v, v, v, ..., v[j]) be a path from v = v 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. 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 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 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 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 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, v, v, ..., v[j]) be a path from v = v 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 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, v, v, ..., v[j]) be a path from v = v 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. 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).

## Create an account

Register a new account