Graph Theory 3rd Midterm Terms

Separating Set

For a graph G that is not complete, a set of vertices V such that G - V is not connected

Vertex Connectivity

The minimum size of a separating set; set kappa(K_n) = n - 1

u, v-Separating Set

A separating set V such that u and v are in different components of G - V

Matching

A set M of edges in a graph G such that no two edges in M are incident

Saturates (a set of vertices)

For a matching M in G and a set X of vertices, every vertex in X is incident to an edge in M

Perfect Matching

A set M of pairwise nonincident edges that covers every vertex

Covering

A set of vertices X such that every edge in G is incident to a vertex in X

Adjacency Matrix

For G with vertices v1, …, vn, the n x n matrix with i, j entry equal to 1 if there is an edge from vj to vi and 0 otherwise; for directed or weighted graphs, the i, j entry is the weight of the edge from vj to vi

Eigenvalue (graph)

A scalar lambda for which there exists a nonzero vector v with A(G) v = lambda v

Eigenvector (graph)

A nonzero vector v satisfying A(G) v = lambda v for some scalar lambda

Strongly Connected (network)

For every pair of vertices u and v there exists a walk from u to v in which no edge has weight 0

Probability Vector

A vector that has nonnegative components that sum to 1

Perron Value

For a strongly connected network’s adjacency graph A, there is a positive real number lambda max such that it is an eigenvalue for A and for all eigenvalues lambda, |lambda| <= lambda max

Perron Vector

The vector v with strictly positive entries such that v is both a probability vector and an eigenvector with eigenvalue lambda max