In discrete mathematics, a walk-regular graph is a

simple graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

where the number of closed walks of any length from a vertex to itself does not depend on the choice of vertex.

Equivalent definitions

Suppose that

G

is a simple graph. Let

A

denote the

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple ...

G

V(G)

denote the set of vertices of

G

, and

\Phi_(x)

denote the characteristic polynomial of the vertex-deleted subgraph

G - v

for all

v \in V(G).

Then the following are equivalent: *

G

is walk-regular. *

A^k

is a constant-diagonal matrix for all

k \geq 0.

\Phi_(x) = \Phi_(x)

for all

u, v \in V(G).

Examples

* The

vertex-transitive graph In the mathematical field of graph theory, a vertex-transitive graph is a graph in which, given any two vertices and of , there is some automorphism :f : G \to G\ such that :f(v_1) = v_2.\ In other words, a graph is vertex-transitive ...

s are walk-regular. * The

semi-symmetric graph In the mathematical field of graph theory, a semi-symmetric graph is an undirected graph that is edge-transitive and regular, but not vertex-transitive. In other words, a graph is semi-symmetric if each vertex has the same number of inciden ...

s are walk-regular. * The

distance-regular graph In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and . ...

s are walk-regular. More generally, any simple graph in a homogeneous coherent algebra is walk-regular. * A connected

regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegre ...

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 In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...

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

distance Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...

at most

k,

the number of walks of length

l

from

v

w

depends only on

k

and

l

. For

k=0

these are exactly the walk-regular graphs. If

k

is at least the

diameter In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid fo ...

of the graph, then the

k

-walk regular graphs coincide with the distance-regular graphs. In fact, if

k\ge 2

and the graph has an eigenvalue of multiplicity at most

k

(except for eigenvalues

d

and

-d

, where

d

is the

degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathemati ...

of the graph), then the graph is already distance-regular. Marc Camara et al., "Geometric aspects of 2-walk-regular graphs," ''Linear Algebra and its Applications'' 439(9) (2013), 2692-2710.

References

{{reflist

External links

* Chris Godsil and Brendan McKay
Feasibility conditions for the existence of walk-regular graphs
Algebraic graph theory Graph families Regular graphs