Purchase Solution

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

Not what you're looking for?

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)

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

##### 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 provided by:
###### Education
• AB, Hood College
• PhD, The Catholic University of America
• PhD, The University of Maryland at College Park
###### Recent Feedback
• "Thanks for your assistance. "
• "Thank you. I understand now."
• "Super - Thank You"
• "Very clear. I appreciate your help. Thank you."
• "Great. thank you so much!"

##### Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

##### Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

##### Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

##### Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

##### Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.