Let G, H be graphs such that G is a subgraph of H. Prove or disprove each of the following: (a) alpha(G) <= alpha(H) (b) alpha(G) >= alpha(H) (c) omega(G) <= omega(H) (d) omega(G) >= omega(H)

The stability number, alpha(G), of a graph G is the cardinality of the largest subset S of V(G), the vertex set of G, such that no two of the vertices in S are connected by an edge of G. The clique number, omega(G), of a graph G is the cardinality of the largest subset S of V(G), the vertex set of G, such that every pair of vertices in S are connected by an edge of G. Let G, H be graphs such that G is a subgraph of H. Prove or disprove each of the following: (a) alpha(G) <= alpha(H) (b) alpha(G) >= alpha(H) (c) omega(G) <= omega(H) (d) omega(G) >= omega(H)

Do the following: (a) Show that the graph G = ({a, b, c, d}, {ab, bc, cd}) is self-complementary. (b) Find a self-complementary graph with five vertices. (c) Prove that if a self-complementary graph has n vertices, then either n is congruent to 0 (mod 4) or n is congruent to 1 (mod 4).

Let G be a graph. Then G = (V, E), where V and E are the vertex set and edge set, respectively, of G. The complement of G, which we will refer to as “G bar,” is the graph (V, E bar), where V is the vertex set of G bar (i.e., the vertex set of G bar is identical to the vertex set of G) and E bar is the edge set of G bar. The edge set E bar is defined as follows: For distinct vertices v1, v2, there is an edge that connects v1 and v2 in G bar if and only if there is no edge that connects v1 and v2 in G. Definition: A graph G is self-complementary if G is isomorphic to G bar. Do the following: (a) Show that the graph G = ({a, b, c, d}, {ab, bc, cd}) is self-complementary. (b) F... click for more

Find a graph G on five vertices such that omega(G) < 3 and omega (G bar) < 3, where “G bar” is the complement of G.

Let G be a graph. Then G = (V, E), where V and E are the vertex set and edge set, respectively, of G. The clique number of G, omega(G), is the cardinality of the largest subset S of V such that every pair of vertices in S are connected by an edge of G. The complement of G, which we will refer to as “G bar,” is the graph (V, E bar), where V is the vertex set of G bar (i.e., the vertex set of G bar is identical to the vertex set of G) and E bar is the edge set of G bar. The edge set E bar is defined as follows: For distinct vertices v1, v2, there is an edge that connects v1 and v2 in G bar if and only if there is no edge that connects v1 and v2 in G. Find a graph G on five vertices... click for more

Context Free Grammar Problem

Please see attached...sorry looks to be an html problem.

Grammar Induction

Consider the grammar 1) -> |epsilon 2) -> 0|1|2|3|4|5|6|7|8|9 Use induction to show that the number of strings in L() of length n is equal to 10^n