Average Resistance of Toroidal Graphs

Wilbert Samuel Rossi, Paolo Frasca, Fabio Fagnani

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

Abstract

The average effective resistance of a graph is a relevant performance index in many applications, including distributed estimation and control of network systems. In this paper, we study how the average resistance depends on the graph topology and specifically on the dimension of the graph. We concentrate on d-dimensional toroidal grids, and we exploit the connection between resistance and Laplacian eigenvalues. Our analysis provides tight estimates of the average resistance, which are key to studying its asymptotic behavior when the number of nodes grows to infinity. In dimension two, the average resistance diverges: in this case, we are able to capture its rate of growth when the sides of the grid grow at different rates. In higher dimensions, the average resistance is bounded uniformly in the number of nodes: in this case, we conjecture that its value is of order 1/d for large d. We prove this fact for hypercubes and when the side lengths go to infinity.

Original languageEnglish
Pages (from-to)2541-2557
Number of pages17
JournalSIAM Journal on Control and Optimization
Volume53
Issue number4
DOIs
Publication statusPublished - 2015
Externally publishedYes

Keywords

  • Consensus
  • Effective resistance
  • Graph dimension
  • Large graphs
  • Relative estimation

Cite this