Graph Theory - Terminology 3

WALKS, PATHS, AND CIRCUITS

 A walk is defined as a finite alternating sequence of vertices and edges, beginning and ending with vertices, such that each edge is incident with the vertices preceding and following it. No edge appears (is covered or traversed) more than once in a walk. A vertex, however, may appear more than once.

A walk is also referred to as an edge train or a chain. The set of vertices and edges constituting a given walk in a graph G is clearly a subgraph of G.

Vertices with which a walk begins and ends are called its terminal vertices.

It is possible for a walk to begin and end at the same vertex. Such a walk is called a closed walk. A walk that is not closed (i.e., the terminal vertices are distinct) is called an open walk

An open walk in which no vertex appears more than once is called a path (or a simple path or an elementary path). A path does not intersect itself. The number of edges in a path is called the length of a path.

An edge which is not a self-loop is a path of length one.

The terminal vertices of a path are of degree one, and the rest of the vertices (called intermediate vertices) are of degree two.

A closed walk in which no vertex (except the initial and the final vertex) appears more than once is called a circuit. That is, a circuit is a closed, nonintersecting walk. Every vertex in a circuit is of degree two; again, if the circuit is a subgraph of another graph, one must count degrees contributed by the edges in the circuit only.

Resource: Graph Theory with Applications to Engineering & Computer Science NARSINGH DEO