Average Resistance of Toroidal Graphs

Wilbert Samuel Rossi, Paolo Frasca, Fabio Fagnani

    Research output: Contribution to journalArticleAcademicpeer-review

    3 Citations (Scopus)
    117 Downloads (Pure)

    Abstract

    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 study 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

    Keywords

    • Graph dimension
    • Relative estimation
    • METIS-315542
    • Effective resistance
    • Large graphs
    • Consensus
    • EWI-26722

    Fingerprint

    Dive into the research topics of 'Average Resistance of Toroidal Graphs'. Together they form a unique fingerprint.

    Cite this