Maximum walk entropy implies walk regularity

Estrada, Ernesto and de la Pena, Jose Antonio (2014) Maximum walk entropy implies walk regularity. Linear Algebra and its Applications, 458. pp. 542-547. ISSN 0024-3795 (

[thumbnail of Estrada-laPena-LAA-2014-Maximum-walk-entropy-implies-walk-regularity]
PDF. Filename: Estrada_laPena_LAA_2014_Maximum_walk_entropy_implies_walk_regularity.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo

Download (410kB)| Preview


The notion of walk entropy SV(G,β)SV(G,β) for a graph G at the inverse temperature β was put forward recently by Estrada et al. (2014) [7]. It was further proved by Benzi [1] that a graph is walk-regular if and only if its walk entropy is maximum for all temperatures β∈Iβ∈I, where I is a set of real numbers containing at least an accumulation point. Benzi [1] conjectured that walk regularity can be characterized by the walk entropy if and only if there is a β>0β>0 such that SV(G,β)SV(G,β) is maximum. Here we prove that a graph is walk regular if and only if the View the MathML sourceSV(G,β=1)=lnn. We also prove that if the graph is regular but not walk-regular View the MathML sourceSV(G,β)<lnn for every β>0β>0 and View the MathML sourcelimβ→0SV(G,β)=lnn=limβ→∞SV(G,β). If the graph is not regular then View the MathML sourceSV(G,β)≤lnn−ϵ for every β>0β>0, for some ϵ>0ϵ>0.