Maximum walk entropy implies walk regularity

Ernesto Estrada, Jose Antonio de la Pena

Research output: Contribution to journalArticle

3 Citations (Scopus)
125 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)542-547
Number of pages6
JournalLinear Algebra and its Applications
Volume458
Early online date9 Jul 2014
DOIs
Publication statusPublished - 1 Oct 2014

Fingerprint

Walk
Entropy
Regularity
Imply
Graph in graph theory
If and only if
Temperature
Accumulation point

Keywords

  • walk-regularity
  • graph walks
  • graph entropies

Cite this

Estrada, Ernesto ; de la Pena, Jose Antonio. / Maximum walk entropy implies walk regularity. In: Linear Algebra and its Applications. 2014 ; Vol. 458. pp. 542-547.
@article{b5294ca0f3db40f5aec4e40ad4957f2d,
title = "Maximum walk entropy implies walk regularity",
abstract = "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,β)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.",
keywords = "walk-regularity, graph walks, graph entropies",
author = "Ernesto Estrada and {de la Pena}, {Jose Antonio}",
year = "2014",
month = "10",
day = "1",
doi = "10.1016/j.laa.2014.06.030",
language = "English",
volume = "458",
pages = "542--547",
journal = "Linear Algebra and its Applications",
issn = "0024-3795",

}

Maximum walk entropy implies walk regularity. / Estrada, Ernesto; de la Pena, Jose Antonio.

In: Linear Algebra and its Applications, Vol. 458, 01.10.2014, p. 542-547.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Maximum walk entropy implies walk regularity

AU - Estrada, Ernesto

AU - de la Pena, Jose Antonio

PY - 2014/10/1

Y1 - 2014/10/1

N2 - 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,β)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.

AB - 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,β)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.

KW - walk-regularity

KW - graph walks

KW - graph entropies

UR - http://www.sciencedirect.com/science/article/pii/S0024379514003991

U2 - 10.1016/j.laa.2014.06.030

DO - 10.1016/j.laa.2014.06.030

M3 - Article

VL - 458

SP - 542

EP - 547

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

SN - 0024-3795

ER -