Second Oral Exam Flashcards
What is a join?
How is it denoted?
A join of two graphs G and H is a graph on the vertex set V(G) U V(H) that is obtained by adding the edges {uv: u » V(G) and v»V(H)} to the disjoint union of G and H. Denoted G + H.
What is alpha’(G)?
The maximum size of a matching.
What is alpha(G)
The maximum size of an independent set.
What is ß’(G)
The minimum size of an edge cover.
What is ß(G)
The minimum size of a vertex cover.
What is a factor of G?
It is a spanning subgraph of G.
What is a k-factor?
A spanning k-regular subgraph.
What is o(G)?
The number of odd order components of G.
What is the connectivity of a graph?
How is it denoted?
The minimum size of a vertex cut. Denoted Kappa(G)
What is k-connected?
A graph is k-connected if the connectivity is at LEAST k. (thus there is no cut set of k-1 or less.)
What is edge connectivity?
How is it denoted?
The minimum size of an edge cut
Kappa’(G)
What is the relation of connectivity, edge connectivity, and the minimum degree of G?
(Kappa(G), Kappa’(G), ∂(G))
Kappa(G) ≤ Kappa’(G) ≤ ∂(G)
What is a vertex cover of a graph G?
a set Q » V(G) that contains at least one endpoint of every edge of G. We often say the vertices of Q cover E(G).
What is the Konig-Egerváry theorem?
If G is a bipartite graph, then the maximum size of a matching in G equals the minimum size of a vertex cover of G.
alpha’(G) = ß(G)
What is an edge cover in a graph G?
A set L of edges such that every vertex of G is incident to some edge of L.
