Kemeny's constant and the effective graph resistance

Xiangrong Wang*, Johan L.A. Dubbeldam, Piet Van Mieghem

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

22 Citations (Scopus)
42 Downloads (Pure)

Abstract

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.

Original languageEnglish
Pages (from-to)231-244
Number of pages14
JournalLinear Algebra and Its Applications
Volume535
DOIs
Publication statusPublished - 2017

Bibliographical note

Accepted Author Manuscript

Keywords

  • Effective graph resistance or Kirchhoff index
  • Kemeny constant
  • Moore–Penrose pseudo-inverse
  • Multiplicative degree-Kirchhoff index
  • Spectral graph theory

Fingerprint

Dive into the research topics of 'Kemeny's constant and the effective graph resistance'. Together they form a unique fingerprint.

Cite this