DMGT

Discussiones Mathematicae Graph Theory 26(3) (2006) 431-437
DOI: https://doi.org/10.7151/dmgt.1335

A LOWER BOUND ON THE INDEPENDENCE NUMBER OF A GRAPH IN TERMS OF DEGREES

Jochen Harant

Institut für Mathematik, TU Ilmenau
98684 Ilmenau, Germany

Ingo Schiermeyer

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: independence, stability, algorithm.

2000 Mathematics Subject Classification: 05C69, 05C85.

References

[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).

Received 28 November 2005
Revised 28 June 2006