Explore BrainMass

# Alpha(G) and omega(G) for a subgraph G of a graph H

Not what you're looking for? Search our solutions OR ask your own Custom question.

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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)

https://brainmass.com/math/basic-algebra/alpha-g-and-omega-g-for-a-subgraph-g-of-a-graph-h-28051

#### 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.49