PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2006 | 26 | 3 | 431-437
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
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
Wydawca
Rocznik
Tom
26
Numer
3
Strony
431-437
Opis fizyczny
Daty
wydano
2006
otrzymano
2005-11-28
poprawiono
2006-06-28
Twórcy
  • Institut für Mathematik, TU Ilmenau, 98684 Ilmenau, Germany
  • 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
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.