Walk-regular graph

Equivalent definitions

• is walk-regular.
• is a constant-diagonal matrix for all
• for all

  Examples

• The vertex-transitive graphs are walk-regular.
• The semi-symmetric graphs are walk-regular.
• The distance-regular graphs are walk-regular. More generally, any simple graph in a homogeneous coherent algebra is walk-regular.
• A connected regular graph is walk-regular if:
• * It has at most four distinct eigenvalues.
• * It is triangle-free and has at most five distinct eigenvalues.
• * It is bipartite and has at most six distinct eigenvalues.

  Properties

• A walk-regular graph is necessarily a regular graph.
• Complements of walk-regular graphs are walk-regular.
• Cartesian products of walk-regular graphs are walk-regular.
• Categorical products of walk-regular graphs are walk-regular.
• Strong products of walk-regular graphs are walk-regular.
• In general, the line graph of a walk-regular graph is not walk-regular.