Walk-regular graph

Short description: Mathematical Graph

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Walk-regular graph" – news · newspapers · books · scholar · JSTOR (October 2019) (Learn how and when to remove this template message)

|

In discrete mathematics, a walk-regular graph is a simple graph where the number of closed walks of any length from a vertex to itself does not depend on the choice of vertex.

## Contents

* 1 Equivalent definitions
* 2 Examples
* 3 Properties
* 4 [math]\displaystyle{ k }[/math]-walk-regular graphs
* 5 References
* 6 External links

## Equivalent definitions

Suppose that [math]\displaystyle{ G }[/math] is a simple graph. Let [math]\displaystyle{ A }[/math] denote the adjacency matrix of [math]\displaystyle{ G }[/math], [math]\displaystyle{ V(G) }[/math] denote the set of vertices of [math]\displaystyle{ G }[/math], and [math]\displaystyle{ \Phi_{G - v}(x) }[/math] denote the characteristic polynomial of the vertex-deleted subgraph [math]\displaystyle{ G - v }[/math] for all [math]\displaystyle{ v \in V(G). }[/math]Then the following are equivalent:

* [math]\displaystyle{ G }[/math] is walk-regular.
* [math]\displaystyle{ A^k }[/math] is a constant-diagonal matrix for all [math]\displaystyle{ k \geq 0. }[/math]
* [math]\displaystyle{ \Phi_{G - u}(x) = \Phi_{G - v}(x) }[/math] for all [math]\displaystyle{ u, v \in V(G). }[/math]

## Examples

* The vertex-transitive graphs are walk-regular.
* The semi-symmetric graphs are walk-regular.[1][unreliable source]
* 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:[dubious - discuss][citation needed]
* 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.

## [math]\displaystyle{ k }[/math]-walk-regular graphs

A graph is [math]\displaystyle{ k }[/math]-walk regular if for any two vertices [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math] of graph-distance [math]\displaystyle{ \mathrm{dist}(v,w)\le k }[/math] the number of walks of length [math]\displaystyle{ \ell }[/math] from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ w }[/math] depends only of [math]\displaystyle{ k }[/math] and [math]\displaystyle{ \ell }[/math]. [2]

For [math]\displaystyle{ k=0 }[/math] these are exactly the walk-regular graphs.

If [math]\displaystyle{ k }[/math] is at least the diameter of the graph, then the [math]\displaystyle{ k }[/math]-walk regular graphs coincide with the distance-regular graphs. In fact, if [math]\displaystyle{ k\ge 2 }[/math] and the graph has an eigenvalue of multiplicity at most [math]\displaystyle{ k }[/math] (except for eigenvalues [math]\displaystyle{ d }[/math] and [math]\displaystyle{ -d }[/math], where [math]\displaystyle{ d }[/math] is the degree of the graph), then the graph is already distance-regular. [3]

## References

1. ↑ "Are there only finitely many distinct cubic walk-regular graphs that are neither vertex-transitive nor distance-regular?". https://mathoverflow.net/a/264155.
2. ↑ Dalfó, Cristina, Miguel Angel Fiol, and Ernest Garriga. "On k-Walk-Regular Graphs." the electronic journal of combinatorics (2009): R47-R47.
3. ↑ Camara, Marc, et al. "Geometric aspects of 2-walk-regular graphs." Linear Algebra and its Applications 439.9 (2013): 2692-2710.

## External links

* Chris Godsil and Brendan McKay, Feasibility conditions for the existence of walk-regular graphs.

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=3362936"