A new lower bound on the independence number of a graph

  • Omar Kettani
    • Categories Graphs and Matroids Tags , , Short URL: https://optimization-online.org/?p=11006

    For a given connected graph G on n vertices and m edges, we prove that its independence number α(G) is at least ((2m+n+2) -sqrt(sqr(2m+n+2)-16sqr(n)))/8.

    Article

    Download

    View PDF