Download PDF - A lower bound on the independence number of a graph in terms of degreesAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

A lower bound on the independence number of a graph in terms of degrees

Authors 1, 2

Affiliations

  1. Institut für Mathematik, TU Ilmenau, 98684 Ilmenau, Germany
  2. Institut für Diskrete Mathematik und Algebra, TU Bergakademie Freiberg, 09596 Freiberg, Germany

Abstract

For a connected and non-complete graph, a new lower bound on its independence number is proved. It is shown that this bound is realizable by the well known efficient algorithm MIN.

Keywords

ENG
independence, stability, algorithm

Bibliography

  1. E. Bertram and P. Horak, Lower bounds on the independence number, Geombinatorics V (1996) 93-98.
  2. Y. Caro, New results on the independence number (Technical Report. Tel-Aviv University, 1979).
  3. Y. Caro and Z. Tuza, Improved lower bounds on k-independence, J. Graph Theory 15 (1991) 99-107, doi: 10.1002/jgt.3190150110.
  4. S. Fajtlowicz, On the size of independent sets in graphs, Proc. 9th S-E Conf. on Combinatorics, Graph Theory and Computing, Boca Raton 1978, 269-274.
  5. S. Fajtlowicz, Independence, clique size and maximum degree, Combinatorica 4 (1984) 35-38, doi: 10.1007/BF02579154.
  6. J. Harant, A lower bound on the independence number of a graph, Discrete Math. 188 (1998) 239-243, doi: 10.1016/S0012-365X(98)00048-X.
  7. J. Harant and I. Schiermeyer, On the independence number of a graph in terms of order and size, Discrete Math. 232 (2001) 131-138, doi: 10.1016/S0012-365X(00)00298-3.
  8. O. Murphy, Lower bounds on the stability number of graphs computed in terms of degrees, Discrete Math. 90 (1991) 207-211, doi: 10.1016/0012-365X(91)90357-8.
  9. S.M. Selkow, A Probabilistic lower bound on the independence number of graphs, Discrete Math. 132 (1994) 363-365, doi: 10.1016/0012-365X(93)00102-B.
  10. J.B. Shearer, A note on the independence number of triangle-free graphs, Discrete Math. 46 (1983) 83-87, doi: 10.1016/0012-365X(83)90273-X.
  11. J.B. Shearer, A note on the independence number of triangle-free graphs, II, J. Combin. Theory (B) 53 (1991) 300-307, doi: 10.1016/0095-8956(91)90080-4.
  12. V.K. Wei, A lower bound on the stability number of a simple graph (Bell Laboratories Technical Memorandum 81-11217-9, Murray Hill, NJ, 1981).
Discussiones Mathematicae Graph Theory
2006/26/3
Export to PBN, Opens in new tab
Pages:
431-437
Main language of publication
English
Received
2005-11-28
Accepted
2006-06-28
Published
2006

DOI: 10.7151/dmgt.1335

Exact and natural sciences