Ch Independence Sets and Covers Flashcards
Defn/ A set S subset of V(G) is an independent set if:
If no two vertices in S are adjacent.
Thm/ S is an independent set, IFF V/S is a cover, where V/s is S^C in V(G)
Pf/ (V/S cover => S indep set)
BWOC, suppose V/S is a cover but S not indep. Thus, there exists vert v,w in S, that are adjacent, AKA v,w in E(G).
Then, neither v,w are in V/S. So vw doesn’t have an end in V/w, so it is not a cover. Contradiction.
(S indep. => V/S cover)
BWOC, suppose S is indep, but V/S is not a cover. There exists an edge vw s.t. v,w not in V/S.
Then, v,w are in S, but they are adjacent, so S is not independent. Contradict.
Defn/ The independence number alpha(G) is:
the max size of an independent set.
Defn/ The covering number beta(G) is:
the minimum size of a covering for G.
Thm/ alpha(G) + beta(G) = v = order
Pf/ Let S be a max indep set, K be min cover.
By prev, the V/K is some indep set, and V/S is some covering.
V - |K| = |V/K| <= alpha
V - |S| = |V/S| >= beta
Implies:
v <= alpha + |K|
=> v<= alpha + beta
v >= beta + |S|
=> v >= beta + alpha
=> v = alpha + beta
Defn/ For a graph G, G^C (compliment graph) is:
is a graph w/ same vertex set, and the edge set is E(K.n)/E(G)
Defn/ A clique is:
is a complete subgraph of G
Thm/ S is a clique in G IFF it is an independent set in G^C.
Pf/ (S Clique => S indep in G^C).
If u,v in S, then uv is in G.
uv not edge in E(G^C)
b/c u,v arbitrary, S indep in G.
(indep. => clique). Set S is indep in G^C, so u,v in S, then there is no uv edge in G^C. So, uv edge in S, since u,v arbitrary, S is a clique.
Defn/ G is alpha critical if:
if alpha(G-e) > alpha(G) for all edges e in E(G). AKA, remove any edges and the maximum independence number goes up
Defn/ G is beta-critical if:
beta(G-e) < beta(G) for all edges e in E(G). AKA, if you take away any edges, you’ll find that the minimum covering number goes down, so makes it easier to cover all edges.
Thm/ If G is B-critical, it has no cut vertex.
So, it has no vertex that removing it will disconnect the graph.
Thm/ G is bipartite IFF for any subgraph H, alpha(H) >= V(H)/2
Pf/ see if needed, long.
Thm/ If G is k-regular and of even order v>=4, then either G or G^C is Ham.
Pf/ If K >=2, graph is Ham by prev. thm.
Else, K<2. This this case, G^C is v-k-1 regular.
Vertex degrees satisfy:
v-k-1 > v- v/2 -1 = v/2 - 1
If v even, degrees are >= v/2, so G^C is Ham. by same prev. thm.
Defn/ The Ramsey number r(m,n) is:
is the minimum order of a graph s.t. G has a clique of size m, or G^C has a clique of size n.
Thm/ r(3,3) = 6
Pf/ If r(3,3) = 5, we can find counterexample, so doesnt work for 5.
For a graph G of order 6, let v be vert.
Then, either degv>=3 in G or in G^C
WLOG, suppose that v.1,v.2,v.3 are adjacent to v. Then, any two of those that are connected forms a triangle/clique in G.
If none connected, those 3 form an indep set, so are a clique in G^C
