Term
|
Definition
| a set of edges without common vertices |
|
|
Term
|
Definition
| a matching M such that every vertex is incident with an edge of M |
|
|
Term
|
Definition
| a matching which matches all vertices of the graph |
|
|
Term
|
Definition
| a matching that contains the largest possible number of edges |
|
|
Term
|
Definition
| a matching that is not a proper subset of any other matching in a graph |
|
|
Term
|
Definition
| a path whose edges are alternately in a matching and not in the matching |
|
|
Term
|
Definition
| a vertex is incident with one of the edges of the matching |
|
|
Term
|
Definition
| a vertex is not incident with one of the edges of the matching |
|
|
Term
|
Definition
| an alternating path joining 2 M-unmatched vertices |
|
|
Term
|
Definition
| the number of edges in a shortest path connecting them |
|
|
Term
|
Definition
| the greatest geodesic distance between 2 vertices |
|
|
Term
|
Definition
| a vertex whose distance between another vertex is the eccentricity |
|
|
Term
| Mutually Eccentric Vertices |
|
Definition
| 2 vertices whose distance is the eccentricity of the graph |
|
|
Term
|
Definition
| the minimum eccentricity of any vertex |
|
|
Term
|
Definition
| the set of all vertices of minimum eccentricity |
|
|
Term
|
Definition
| the maximum eccentricity of any vertex in the graph |
|
|
Term
|
Definition
| the set of vertices with max eccentricity |
|
|
Term
|
Definition
| 2 vertices whose distance is the diameter of a graph |
|
|
Term
|
Definition
| a geodesic joining a diametral pair of vertices |
|
|
Term
|
Definition
| a geodesic joining a central vertex to one of its eccentric vertices |
|
|
Term
|
Definition
| a path between 2 vertices of min length |
|
|
Term
|
Definition
| any vertex that when removed increases the number of connected components. |
|
|
Term
| Vertex Connectivity of a Graph |
|
Definition
| the min number of vertices whose deletion makes a graph disconnected or trival |
|
|
Term
| Edge Connectivity of a Graph |
|
Definition
| the min number of edges whose deletion makes a graph disconnected or trivial |
|
|
Term
|
Definition
| a graph whose vertex connectivity is equal or greater than k |
|
|
Term
|
Definition
| a subgraph that has no cut vertex |
|
|
Term
|
Definition
| a maximal connected subgraph |
|
|
Term
|
Definition
| a graph with an Eulerian circuit |
|
|
Term
|
Definition
| a trail in a graph which visits every edge exactly once and starts and ends on the same vertex |
|
|
Term
|
Definition
| a graph that has an Eulerian trail but not an Eulerian circuit |
|
|
Term
|
Definition
| a cycle in an symmetric graph which visits each vertex exactly once and also returns to the starting vertex |
|
|
Term
|
Definition
| A graph that contains a Hamiltonian cycle |
|
|
Term
|
Definition
| a graph that has a Hamiltonian path but no Hamiltonian cycle |
|
|
Term
|
Definition
| a matching in a graph is max iff there is no M-augmenting path in the graph |
|
|
Term
|
Definition
1. d(u,v)>=0 and d(u,v)=0 iff u=v
2. d(u,v)=d(v,u) for all u,v
3. d(u,v)<=d(u,w)+d(w,u) for all u,v,w |
|
|
Term
|
Definition
| The center of a connected graph belongs to a single block of the graph |
|
|
Term
| Characterization of Eulerian Graphs |
|
Definition
| a graph is eulerian iff the graph is connected and every vertex has an even degree |
|
|
Term
| Characterization of Semi-eulerian Graphs |
|
Definition
| a connected graph whose has exactly 2 vertices of odd degree, and an eulerain trail connects them |
|
|
