Journal of Combinatorics

Volume 14 (2023)

Number 4

New results and open problems on subgraph centrality

Pages: 425 – 444



Nikita Deniskin (Scuola Normale Superiore, Pisa, Italy)

Michele Benzi (Scuola Normale Superiore, Pisa, Italy)


Subgraph centrality, introduced by Estrada and Rodríguez-Velázquez in [16], has become a widely used centrality measure in the analysis of networks, with applications in biology, neuroscience, economics and many other fields. It is also worthy of study from a strictly mathematical point of view, in view of its connections to topics in spectral graph theory, number theory, analytic matrix functions, and combinatorics. In this paper, we present some new results and a list of open questions about subgraph centrality and other node centrality measures based on graph walks.


cospectral vertices, graph walks, subgraph centrality, interlacing

2010 Mathematics Subject Classification

05C50, 15A16

Received 12 November 2021

Accepted 5 September 2022

Published 14 April 2023