Abstract
In graph theory, walk-regularity represents a high degree of symmetry where every vertex is involved in the same number of closed walks of any length. It has long been conjectured that a graph achieves maximum walk entropy if and only if it is walk-regular. This paper disproves this notion by constructing a 24-vertex non-regular graph, $H_4$, which exhibits maximum entropy at specific "temperatures." We show that while non-regular graphs can "fake" perfect symmetry, they can only do so at a finite number of parameter values.
Introduction
Walk-regularity is a structural property requiring that for every length $\ell$, the number of closed walks of length $\ell$ starting and ending at vertex $v$ is independent of $v$. This is closely linked to walk entropy, an algebraic measure of vertex centrality. Benzi (2014) and Estrada et al. conjectured that if a graph's walk entropy is maximized at any inverse temperature $\beta > 0$, the graph must be walk-regular. This paper challenges this assumption by exploring whether a non-regular graph can achieve maximum entropy.
The $H_4$ Construction
To test these conjectures, the authors introduced a family of graphs $H_m$. The specific counterexample, $H_4$, consists of 24 vertices. It is built from four isolated vertices and five cliques ($K_4$), connected via a perfect matching.
The resulting graph is not even degree-regular, containing vertices of both degree 4 and degree 5. Despite this lack of basic regularity, the graph's spectral properties allow for "accidental" maximum entropy.
Spectral Analysis and Methodology
The authors analyzed the adjacency matrix $A_{H_4}$ to derive the diagonal entries of the matrix exponential $e^{\beta A}$, which determines vertex centrality.
By examining the eigenvalues and eigenvectors, the researchers proved that the centrality functions for different vertex types must cross at specific values of $\beta$. At these crossing points, the entropy function reaches its theoretical maximum, $\log 24$, making all vertices appear identical in terms of walk-based centrality.
Key Results and Insights
The primary contribution of this work is the formal disproof of conjectures by Benzi and Estrada et al. The existence of $H_4$ demonstrates that maximum walk entropy does not imply walk-regularity or even degree-regularity.
Numerical analysis identifies two such "Goldilocks" points for $H_4$ at $\beta \approx 0.499$ and $\beta \approx 1.912$. The authors further established a Classification Theorem: while "fake" symmetries exist, they are rare. For any non-walk-regular graph, there are at most a finite number of $\beta$ values that maximize entropy. Consequently, a randomly chosen $\beta$ will almost certainly distinguish between walk-regular and non-walk-regular graphs.
Conclusion and Future Directions
This research clarifies the boundaries between algebraic graph properties and information-theoretic measures. Future work remains to determine if maximum entropy can occur at rational values of $\beta$ and to prove the conjecture that the number of such accidental maximums is bounded by $n_G - 1$.
Summary updated