Share
Explore BrainMass

Alpha(G) and omega(G) for a subgraph G of a graph 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)

Attachments

Solution Preview

Statement (a) is true.

Proof of (a):

Since G is a subgraph of H, every pair of vertices v1, v2 of G that are not connected by an edge in G are also not connected by an edge in H.

Thus every 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 is also a subset of V(H), the vertex set of H, such that no two of the vertices in S are connected by an edge of H.

Hence the cardinality of the largest subset S of V(G) such that no two of the vertices in S are ...

Solution Summary

Step-by-step proofs are given for the given statements that are true. Counterexamples (with detailed justifications) for the given statements that are false are provided in an attached .doc file.

$2.19