Pergunta

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$?

Foi útil?

Solução

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)$.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top