Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949794 | Discrete Applied Mathematics | 2017 | 10 Pages |
Abstract
The independence number of a graph G is the maximum cardinality of an independent set of vertices in G. In this paper we obtain several new lower bounds for the independence number of a graph in terms of its order, size and maximum degree, and characterize graphs achieving equalities for these bounds. Our bounds improve previous bounds for graphs with large maximum degree.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Nader Jafari Rad, Elahe Sharifi,