TOPICS
Search

Walk


A walk is a sequence v_0, e_1, v_1, ..., v_k of graph vertices v_i and graph edges e_i such that for 1<=i<=k, the edge e_i has endpoints v_(i-1) and v_i (West 2000, p. 20). The length of a walk is its number of edges.

A u,v-walk is a walk with first vertex u and last vertex v, where u and v are known as the endpoints. Every u,v-walk contains a u,v-graph path (West 2000, p. 21).

A walk is said to be closed if its endpoints are the same. The number of (undirected) closed k-walks in a graph with adjacency matrix A is given by Tr(A^k), where Tr(A) denotes the matrix trace. In order to compute the number c_k of k-cycles, all closed k-walks that are not cycles must be subtracted. Similarly, to compute the number p_k of graph paths, all k-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.


See also

Graph Cycle, Graph Path, Hamiltonian Walk, Random Walk, Trail

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Walk

Cite this as:

Weisstein, Eric W. "Walk." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Walk.html

Subject classifications