A lower bound on independence in terms of degrees

We prove a new lower bound on the independence number of a simple connected graph in terms of its degrees.

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2011-06, Vol.159 (10), p.966-970
Main Author: Harant, Jochen
Format: Article
Language:English
Subjects:
Connected graph
Graphs
Independence
Lower bounds
Mathematical analysis
Stability
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We prove a new lower bound on the independence number of a simple connected graph in terms of its degrees.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2011.03.003