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.