Walk-regular graph

Short description: Mathematical Graph

In graph theory, a walk-regular graph is a simple graph where the number of closed walks of any length ℓ from a vertex to itself does only depend on ℓ but not depend on the choice of vertex.[1] Walk-regular graphs can be thought of as a spectral graph theory analogue of vertex-transitive graphs. While a walk-regular graph is not necessarily very symmetric, all its vertices still behave identically with respect to the graph's spectral properties.

## Contents

* 1 Equivalent definitions
* 2 Examples
* 3 Properties
* 4 k-walk-regular graphs
* 5 References

## Equivalent definitions

Suppose that G is a simple graph. Let A denote the adjacency matrix of G, V(G) denote the set of vertices of G, and ΦG−v(x) denote the characteristic polynomial of the vertex-deleted subgraph G−v for all v∈V(G).Then the following are equivalent:

* G is walk-regular.
* Ak is a constant-diagonal matrix for all k≥0.
* ΦG−u(x)=ΦG−v(x) for all u,v∈V(G).

## Examples

* The vertex-transitive graphs are walk-regular.[2]
* The distance-regular graphs are walk-regular.[1] 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.[2]

## Properties

* A walk-regular graph is necessarily a regular graph, since the number of closed walks of length two starting at any vertex is twice the vertex's degree.[1]
* Complements of walk-regular graphs are walk-regular. [3]
* Cartesian products of walk-regular graphs are walk-regular.[3]
* Categorical products of walk-regular graphs are walk-regular.[3]
* Strong products of walk-regular graphs are walk-regular. [3]
* In general, the line graph of a walk-regular graph is not walk-regular.

## k-walk-regular graphs

A graph is k-walk-regular if for any two vertices v and w of distance at most k, the number of walks of length ℓ from v to w depends only on k and ℓ.[1][4]

The class of 0-walk-regular graphs is exactly the class of walk-regular graphs

In analogy to walk-regular graphs generalizing vertex-transitive graphs, 1-walk-regular graphs can be thought of as generalizing symmetric graphs, that is, graphs that are both vertex- and edge-transitive. For example, the Hoffman graph is 1-walk-regular but not symmetric.

If k is at least the diameter of the graph, then the k-walk-regular graphs coincide with the distance-regular graphs. In fact, if k≥2 and the graph has an eigenvalue of multiplicity at most k (except for eigenvalues d and −d, where d is the degree of the graph), then the graph is already distance-regular.[5]

## References

1. ↑ 1.0 1.1 1.2 1.3 Dalfó, C.; Fiol, M.A.; Garriga, E. (2009). "On k-Walk-Regular Graphs". Electronic Journal of Combinatorics 16 (1): #R47. doi:10.37236/136. https://upcommons.upc.edu/server/api/core/bitstreams/feeffccf-e0d3-4980-a811-ea2314c1b31b/content.
2. ↑ 2.0 2.1 Brouwer, Andries E.; Haemers, Willem H. (2012), "Graphs with few eigenvalues", Spectra of Graphs, Universitext, New York, NY: Springer, pp. 217–218, doi:10.1007/978-1-4614-1939-6, ISBN 978-1-4614-1939-6, https://aeb.win.tue.nl/2WF02/spectra.pdf
3. ↑ 3.0 3.1 3.2 3.3 Godsil, C.D.; McKay, B.D. (April 1980). "Feasibility conditions for the existence of walk-regular graphs". Linear Algebra and Its Applications 30: 51–61. doi:10.1016/0024-3795(80)90180-9.
4. ↑ Dalfó, C.; Fiol, M.A.; Garriga, E. (August 2009). "On t-Cliques in k-Walk-Regular Graphs". Electronic Notes in Discrete Mathematics 34: 579–584. doi:10.1016/j.endm.2009.07.096.
5. ↑ Cámara, Marc; van Dam, Edwin R.; Koolen, Jack H.; Park, Jongyook (November 2013). "Geometric aspects of 2-walk-regular graphs". Linear Algebra and Its Applications 439 (9): 2692–2710. doi:10.1016/j.laa.2013.07.028.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Walk-regular graph. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Walk-regular_graph&oldid=4230807"