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 |
|
|
