Facebook Page
Twitter
RSS
Thanks Thanks:  0
+ Reply to Thread
Results 1 to 1 of 1
  1. MHB Craftsman

    Status
    Offline
    Join Date
    Mar 2017
    Posts
    145
    Thanks
    42 times
    Thanked
    76 times
    #1
    I have already proved that for a graph $G$ with $n$ vertices and $|E(T'(n,q))|$ edges, $\alpha (G) \geq q$. Additionally, if $\alpha (G) = q$ then it must be that $G \cong T'(n,q)$.

    Apparently this is the "dual version" of Turan's Theorem. How does this theorem imply Turan's?

    That $ex(n, K_{p+1}) = |E(T(n,p))|$

    Where:

    - $T'(n,q)$ : $q$ disjoint cliques with size as equal as possible
    - $\alpha (G)$ : independence number of $G$
    - $ex(n, K_{p+1})$ : max number of edges in an n-vertex graph with no $K_{p+1}$ subgraph

  2. # ADS
    Circuit advertisement
    Join Date
    Always
    Posts
    Many
     

Similar Threads

  1. Replies: 2
    Last Post: February 15th, 2019, 04:56
  2. Replies: 2
    Last Post: February 10th, 2019, 01:22
  3. Dual Spaces ... Friedberg et al, Example 4, Section 2.6
    By Peter in forum Linear and Abstract Algebra
    Replies: 2
    Last Post: January 8th, 2019, 07:58
  4. Replies: 2
    Last Post: March 6th, 2016, 22:15
  5. Primal Dual Problems
    By OhMyMarkov in forum Advanced Applied Mathematics
    Replies: 0
    Last Post: April 30th, 2012, 09:03

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards