Czasopismo
Tytuł artykułu
Autorzy
Treść / Zawartość
Pełne teksty:
Warianty tytułu
Języki publikacji
Abstrakty
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
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
431-437
Opis fizyczny
Daty
wydano
2006
otrzymano
2005-11-28
poprawiono
2006-06-28
Twórcy
autor
- Institut für Mathematik, TU Ilmenau, 98684 Ilmenau, Germany
autor
- 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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1335