Often, and in this paper in particular, we restrict V and E to be finite sets. We also require the graphs to be simple, which means we disallow loops (edges of the form (v, v) for some vertex v) and multiple edges from one vertex to another.
For directed graphs we do not count edges (u, v) and (v, u) as multiple edges because they have opposite directions. In fact, we say the edge (u, v) is incident from u, and incident to v. Sometimes we then also say u dominates v. The vertices incident to (respectively, from) v are called the in-neighbors (respectively, out-neighbors) of v. The indegree (resp., outdegree) of a vertex is the number of its in-neighbors (resp., out-neighbors). When there is no confusion, we may refer to the out-neighbors of v as simply its neighbors.
A subgraph [subdigraph for directed graphs] has as its vertex set some subset of the vertex set of the original graph, and every edge in the subgraph is an edge in the original. A maximal subgraph is a subgraph with the maximum possible number of edges (every edge which is in the original and has both endpoints in the vertex set of the subgraph).
The removal of a vertex from a graph results in the subgraph formed by removing the vertex and all the edges incident to it. Removing an edge does not remove any vertices. An edge (u, v) may be subdivided by adding one or more new vertices w1, ..., wn to the vertex set, removing the edge (u, v), and in its place adding the edges (u, w1), Š (wn-1, wn), (wn, v).
We can also speak of longer sequences of vertices joined by edges. A sequence x1 e1 x2 e2 ... xn en xn+1 is called a walk (of length n) whenever all the xi are vertices and each edge ei = (xi, xi+1) joins the two vertices immediately surrounding it in the sequence. For a simple graph, it is enough to list just the vertex sequence, since the edges are then uniquely determined.
A trail is a walk in which no edge is repeated; a path is a walk in which no vertex (and hence no edge) is repeated. A walk or trail is closed if the first and last vertices are the same (xn+1 = x1). A cycle of length n is a closed path x1 e1 x2 ... xn en x1, which we will sometimes write as (x1, x2, ..., xn) to emphasize that it is a cycle and not merely a path. When we speak of the parity of any of these, we mean the parity of the number of edges in the walk, trail, path or cycle in question. A digraph with no cycles at all is acyclic.
Another useful concept in analyzing the structure of graphs is that of connectedness. Loosely speaking, the more connected a graph is, the easier it is to travel along edges in the graph from one vertex to another. A directed graph is (strongly) connected (or just strong) if, for any two vertices x and y of the digraph, there is a path from x to y, and a path from y to x. More generally, a digraph is (strongly) k-connected if the removal of any k-1 or fewer vertices results in a digraph which is still connected. If the underlying undirected graph (formed by disregarding the orientation of each edge) is connected, then the digraph is weakly connected (or just weak). We make no use of this concept in this paper, but mention in passing that a digraph which is not even weakly connected is said to be disconnected, and a weakly connected acyclic directed graph is called a directed tree.
Strongly connected digraphs are of particular interest in directed graph theory. Often it suffices to prove a theorem only for strong digraphs, and then the other cases follow. Each maximal strongly connected subdigraph is called a (strong) component of the digraph. It is not difficult to prove that every vertex of a digraph lies in a unique strong component, and in fact these components can be found in polynomial time.
Each graph has an adjacency matrix associated with it. The adjacency matrix has rows and columns indexed by the vertex set of the graph. The element of this matrix in row u, column v is 1 whenever (u, v) is an edge in the graph, and 0 otherwise. Consequently, the adjacency matrix of an undirected graph is symmetric, but this need not hold for directed graphs. The adjacency matrix provides an alternative form for representing a digraph from the usual vertex and edge sets. Because this representation can be obtained from the other in polynomial time, the two are equivalent from our algorithmic point of view.
The relationships between digraphs and matrices are deep and complex. For example, directed graph theory can be used to calculate the eigenvalues and inverse (when it exists) of a square matrix, and is especially effective when the associated digraph has few edges, which translates into the matrix being sparse (i.e., the matrix has many zeros). [Harary, p. 205]
The relationship between directed graphs and L- and S-matrices is the focus of chapter two. For an excellent introduction to undirected and directed graph theory, the interested reader is directed (no pun intended) to Graph Theory with Applications, by Bondy and Murty.