1
$\begingroup$

How can I find the effective resistance between any two points on a complete bipartite graph $K_{m,n}$? I want to try and identify any equipotential points in order to simplify the problem, but I'm not sure if I'm doing this correctly.

So far I think, if I have two nodes from the same partition of the graph, that I can contract the other partition yielding an effective resistance of $\frac{2}{n}$ where n is the size of the contracted partition.

But when it comes to two vertices which are from different partitions of $K_{m,n}$, I can't seem to figure out how to simplify the problem.

$\endgroup$
1
$\begingroup$

Let $v$ be the vertex in the first ($m$-sized) part of $K_{m,n}$ and let $w$ be the vertex in the second ($n$-sized) part. Say we want to find the effective resistance between $v$ and $w$.

By symmetry, all vertices in the first part other than $v$ have the same voltage potential (or whatever the correct terminology is; I'm a graph theorist, not an electrical engineer), so we can combine them into a single vertex $x$. Similarly, we can combine all vertices in the second part other than $w$ into a single vertex $y$. This gives us a $4$-vertex graph:

enter image description here

This graph is series-parallel. Between $v$ and $y$, we have $n-1$ edges, so the resistance there is $\frac1{n-1}$; between $x$ and $y$, it is $\frac1{(m-1)(n-1)}$; between $x$ and $w$, it is $\frac1{m-1}$. There are two ways to get from $v$ to $w$, so the effective resistance is $$ \frac1{\frac11 + \frac1{\frac1{n-1} + \frac1{(m-1)(n-1)} + \frac1{m-1}}} = \frac1{1 + \frac{(m-1)(n-1)}{m+n-1}} = \frac{m+n-1}{mn}. $$


An alternate solution uses the identity that in any graph $G$, we have $$ \sum_{xy \in E(G)} \frac{R_{xy}^{\text{eff}}}{R_{xy}} = |V(G)|-1. $$ In this problem, $R_{xy}=1$ for all edges; $R_{xy}^{\text{eff}}$ is the same constant $r$ for all edges, by symmetry; the number of edges in $K_{m,n}$ is $mn$ and the number of vertices is $m+n$. So we have $$ \sum_{e \in E(G)} r = |V(G)|-1 \implies r = \frac{|V(G)|-1}{|E(G)|} \implies r = \frac{m+n-1}{mn}. $$


Third solution: the effective resistance between $v$ and $w$, when $vw$ is an edge of the graph, is the probability that a random walk starting at $v$ ends up at $w$ (when it does) by taking the edge $vw$.

In $K_{m,n}$, this can happen in two ways.

  1. The very first step is to go from $v$ to $w$. This happens with probability $\frac1n$.
  2. The first step is something else (which happens with probability $1 - \frac1n$). Then, every time we're on the same side as $v$, we're equally likely to be at any of the $m$ vertices. So the probability that the vertex we get to $w$ from is $v$ is $\frac1m$.

Combining these, we get a probability of $$ \frac1n + \left(1 - \frac1n\right)\frac1m = \frac1n + \frac1m - \frac1{nm} = \frac{m+n-1}{mn}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.