Term
|
Definition
set of pairwise adjacent vertices |
|
|
Term
|
Definition
simple graph whose vertices can be ordered so that two vertices are adjacent iff they are consecutive in the list A walk that has no repeated vertices or edges |
|
|
Term
|
Definition
a graph with an equal number of vertices and edges whose vertices can be placed around a circle so that two vertices are adjacent iff they appear consecutively along the circle |
|
|
Term
|
Definition
For a graph with n vertices, the adjacency matrix is an n x n matrix where element (i,j) is the number of edges in G with endpoints {vi, vj} |
|
|
Term
|
Definition
For a graph with n vetices and m edges, the incidence matrix is an n x m matrix where each element (i,j) is 1 if vi is an endpoint of ej, otherwise 0. |
|
|
Term
|
Definition
Symbol for adjacency matrix |
|
|
Term
|
Definition
Symbol for incidence matrix |
|
|
Term
|
Definition
Length of the shortest cycle of a graph |
|
|
Term
|
Definition
an isomorphism that maps G to G. |
|
|
Term
|
Definition
a graph that for every pair u,v in V(G) there is an automorphism that maps u to v. |
|
|
Term
|
Definition
a walk with no repeated edges |
|
|
Term
|
Definition
maximally conneted subgraph |
|
|
Term
|
Definition
subgraph obtained by removing a vertex/vertices |
|
|
Term
|
Definition
A graph that has a closed trail containing all edges |
|
|
Term
|
Definition
A circuit/trail that contains all edges |
|
|
Term
|
Definition
Graph whose vertices are all of even/odd degree. |
|
|
Term
|
Definition
set of vertices adjacent to a given vertex |
|
|
Term
|
Definition
symbol for neighborhood of vertex v |
|
|
Term
|
Definition
number of vertices in a graph |
|
|
Term
|
Definition
symbol for the order of a graph |
|
|
Term
|
Definition
number of edges in a graph |
|
|
Term
|
Definition
symbol for size of a graph |
|
|
Term
|
Definition
disjoint union of G and H |
|
|
Term
|
Definition
graph consisting of m pairwaise disjoint copies of G |
|
|
Term
|
Definition
G has no induced subgraph isomorphic to H |
|
|
Term
|
Definition
replacement of a pair of edges xy and zw in a simple graph by the edges yz and wx given that yz and wx did not appear in the graph originally |
|
|
Term
distance from vertices u and v |
|
Definition
least length of a u,v path |
|
|
Term
|
Definition
symbol for the distance from u to v |
|
|
Term
|
Definition
length of the longest u,v path for all u,v |
|
|
Term
|
Definition
length of the path from u to the farthest vertex. |
|
|
Term
|
Definition
the eccentricity of the vertex with the smallest eccentricity. |
|
|
Term
|
Definition
subgraph induced by the vertices of minimum eccentricity. |
|
|
Term
|
Definition
set of non-loop edges with no shared endpoints |
|
|
Term
|
Definition
vertices incident to the edges of a matching |
|
|
Term
|
Definition
vertices that are not incident to the edges of a matching |
|
|
Term
|
Definition
a matching that saturates every vertex |
|
|
Term
|
Definition
path that alternates between edges in M and edges not in M |
|
|
Term
|
Definition
M-alternating path whose endpoints are unsaturated |
|
|
Term
|
Definition
set of vertices that contains at least one endpoint of every edge |
|
|
Term
|
Definition
maximum size of independent set of vertices |
|
|
Term
|
Definition
set of edges L such that every vertex is incident to some edge of L. |
|
|
Term
|
Definition
symbol for independence number |
|
|
Term
|
Definition
symbol for maximum size of matching |
|
|
Term
|
Definition
symbol for minimum size of vertex cover |
|
|
Term
|
Definition
symbol for minimum size of edge cover |
|
|
Term
|
Definition
k-regular spanning subgraph of a graph |
|
|
Term
|
Definition
symbol for the number of odd components in H |
|
|
Term
|
Definition
graph obtained from the disjoint union of two graphs, adding every possible edge between them |
|
|
Term
|
Definition
symbol for the join of G and H |
|
|
Term
|
Definition
a set S of vertices such that G - S has more than one component |
|
|
Term
|
Definition
minimum size of a vertex cut such that G - S is disconnected or has only one vertex |
|
|
Term
|
Definition
symbol for the connectivity of a graph G |
|
|
Term
|
Definition
set of edges F such that G - F has more than one component |
|
|
Term
|
Definition
minimum size of an edge cut |
|
|
Term
|
Definition
symbol for edge connectivity of G |
|
|
Term
|
Definition
symbol for an edge cut where the cut is all edges between the sets of vertices S and S' |
|
|
Term
|
Definition
minimal nonempty edge cut |
|
|
Term
internally disjoint paths |
|
Definition
paths from u to v that share no common internal vertex. |
|
|
Term
|
Definition
adding a vertex between the two endpoints of the edge |
|
|
Term
|
Definition
maximum size of a set of pairwise internally disjoint x,y-paths |
|
|
Term
|
Definition
|
|
Term
|
Definition
assigns a value f(e) to each edge e |
|
|
Term
|
Definition
For every edge e, f(e) <= c(e) and the net flow of every vertex other than the source and sink is 0. |
|
|
Term
|
Definition
a digraph with a nonnegative capacity c(e) assigned to every edge e and a distinguished souce vertex s and sink vertex t |
|
|
Term
|
Definition
source to sink path P such that for each e in E(P), if P follows e in the forward direction then f(e) < c(e). If P follows e in the backward direction then f(e) > 0. |
|
|
Term
|
Definition
tolerance of a source to sink path P is equal to the min(ε(e)) where ε(e) equals:
ε(e)=c(e) - f(e) when e is forward on P
ε(e)=f(e) when e is backward on P |
|
|
Term
|
Definition
consists of edges from a source set S to a sink set T where S and T partition the nodes with s in S and t in T.
The capacity of a cut cap(S,T) is the total of the capacities on the edges of S and T |
|
|
Term
|
Definition
symbol for a souce sink cut |
|
|