TY - JOUR

T1 - Kemeny's constant and the effective graph resistance

AU - Wang, Xiangrong

AU - Dubbeldam, Johan L.A.

AU - Van Mieghem, Piet

N1 - Accepted Author Manuscript

PY - 2017

Y1 - 2017

N2 - Kemeny's constant and its relation to the effective graph resistance has been established for regular graphs by Palacios et al. [1]. Based on the Moore–Penrose pseudo-inverse of the Laplacian matrix, we derive a new closed-form formula and deduce upper and lower bounds for the Kemeny constant. Furthermore, we generalize the relation between the Kemeny constant and the effective graph resistance for a general connected, undirected graph.

AB - Kemeny's constant and its relation to the effective graph resistance has been established for regular graphs by Palacios et al. [1]. Based on the Moore–Penrose pseudo-inverse of the Laplacian matrix, we derive a new closed-form formula and deduce upper and lower bounds for the Kemeny constant. Furthermore, we generalize the relation between the Kemeny constant and the effective graph resistance for a general connected, undirected graph.

KW - Effective graph resistance or Kirchhoff index

KW - Kemeny constant

KW - Moore–Penrose pseudo-inverse

KW - Multiplicative degree-Kirchhoff index

KW - Spectral graph theory

UR - http://www.scopus.com/inward/record.url?scp=85029420664&partnerID=8YFLogxK

UR - http://resolver.tudelft.nl/uuid:1f46cc50-c3e6-425c-91bb-d05944301420

U2 - 10.1016/j.laa.2017.09.003

DO - 10.1016/j.laa.2017.09.003

M3 - Article

AN - SCOPUS:85029420664

VL - 535

SP - 231

EP - 244

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

ER -