Walk
A walk is a sequence 
, 
, 
, ..., 
of graph vertices 
and graph edges 
such that for 
, the edge 
has endpoints 
and 
(West 2000, p. 20). The length of a walk is its number of edges.
A 
-walk is a walk with first vertex 
and last vertex 
, where 
and 
are known as the endpoints. Every 
-walk contains a 
-graph path (West 2000, p. 21).
A walk is said to be closed if its endpoints are the same. The number of (undirected) closed 
-walks in a graph with adjacency matrix 
is given by 
, where 
denotes the matrix trace. In order to compute the number 
of 
-cycles, all closed 
-walks that are not cycles must be subtracted. Similarly, to compute the number 
of graph paths, all 
-walks that are not graph paths (because they contain redundant vertices) must be subtracted (cf. Festinger 1949, Ross and Harary 1952).
For a simple graph (which has no multiple edges), a walk may be specified completely by an ordered list of vertices (West 2000, p. 20).
A trail is a walk with no repeated edges.
REFERENCES
Festinger, L. "The Analysis of Sociograms Using Matrix Algebra." Human Relations 2, 153-158, 1949.
Ross, I. C. and Harary, F. "On the Determination of Redundancies in Sociometric Chains." Psychometrika 17, 195-208, 1952.
West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 20-21, 2000.
