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

• Autorzy: Jochen Harant , Ingo Schiermeyer
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

independence   stability   algorithm  

Kategorie tematyczne

• 05C69: Dominating sets, independent sets, cliques
• 05C85: Graph algorithms

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2006
• Tom: 26
• Numer: 3
• Strony: 431-437

Daty

wydano

2006

otrzymano

2005-11-28

poprawiono

2006-06-28

Twórcy

autor

Jochen Harant

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

autor

Ingo Schiermeyer

• Institut für Diskrete Mathematik und Algebra, TU Bergakademie Freiberg, 09596 Freiberg, Germany

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1335