Explore BrainMass

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)

    © BrainMass Inc. brainmass.com November 30, 2021, 12:13 am ad1c9bdddf
    https://brainmass.com/math/basic-algebra/alpha-g-and-omega-g-for-a-subgraph-g-of-a-graph-h-28051

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

    ADVERTISEMENT