2
$\begingroup$

Let $G$ be a $d$-regular expander graph. What is the electrical resistance of $G$? Is it a constant independent of the number of nodes $n$ once $d$ is large enough? If not, can we give matching upper and lower bounds in terms of $n,d$?

$\endgroup$
  • 1
    $\begingroup$ How does electrical resistance end up in graph theory? $\endgroup$ – Raphael Jul 7 '13 at 17:53
  • 1
    $\begingroup$ Electrical resistance is a property of the graph. Roughly speaking, it measures its connectivity. It is also connected to hitting and commute times, hence the random walks tag. $\endgroup$ – maartje Jul 7 '13 at 17:57
  • $\begingroup$ Have you tried generating some examples and plotting the resistance as a function of $n,d$ for several different types of expander graphs? You might want to edit your question to include what you've tried so far. $\endgroup$ – D.W. Jul 7 '13 at 22:16
  • 2
    $\begingroup$ Please define your terms. What is the definition of electrical resistance of an edge/node/subgraph/graph? What is an expander graph? And what does it mean for an an expander graph to be d-regular? $\endgroup$ – Wandering Logic Jul 7 '13 at 23:16
  • $\begingroup$ here is a cool new simons institute article on the basic theory around this subject, some of it very advanced/deep Network Solutions by Klarreich, its all about the graph Laplacian $\endgroup$ – vzn Jul 10 '13 at 19:10
2
$\begingroup$

Next time you ask a question you should try to google it first. I googled "electrical resistance expander graph" and the very first result was a paper stating that $d$-regular graphs have resistance $\Theta(1/d)$.

$\endgroup$
  • $\begingroup$ Thanks. I did google it and perused the abstract of that paper, but missed the reference to expanders. $\endgroup$ – maartje Jul 8 '13 at 9:21

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.