Results 1 to 2 of 2

Math Help - Max size of..

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Max size of..

    I'm asked to:

    a) Find the max size of an independent set of vertices on a particular graph.

    b) Find the max size of a set of pairwise adjacent vertices in G.

    Can someone clarify and tell me 'in English' what is being asked of me?

    This isn't my problem, but lets consider the Peterson Graph so I can see how this is done...

    Thanks a lot!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    You can look up the definitions on Wikipedia. A subset of vertices is called an independent set if no pair of vertices are connected. Maximum independent sets in Petersen graph have 4 vertices (this is called the independence number).

    A set of pairwise adjacent vertices, also called a clique, is a subset of vertices such that every two vertices in the subset are connected. I believe the maximum clique in Petersen graph has size 2.

    Note that "a set is independent if and only if it is a clique in the graph’s complement" (Wikipedia).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Maximum size of G
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 6th 2012, 04:48 AM
  2. sample size
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: November 25th 2011, 02:48 AM
  3. size of null(A)
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 8th 2010, 06:06 PM
  4. Sample size
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: December 1st 2009, 09:05 AM
  5. Size!
    Posted in the Math Challenge Problems Forum
    Replies: 4
    Last Post: November 16th 2009, 03:40 PM

Search Tags


/mathhelpforum @mathhelpforum