Download PDF - Some news about the independence number of a graphAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Some news about the independence number of a graph

Authors 1

Affiliations

  1. Department of Mathematics, Technical University of Ilmenau, D-98684 Ilmenau, Germany

Abstract

For a finite undirected graph G on n vertices some continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the independence number of G.

Keywords

ENG
graph, independence

Bibliography

  1. E. Bertram, P. Horak, Lower bounds on the independence number, Geombinatorics, (V) 3 (1996) 93-98.
  2. R. Boppana, M.M. Halldorsson, Approximating maximum independent sets by excluding subgraphs, BIT 32 (1992) 180-196, doi: 10.1007/BF01994876.
  3. Y. Caro, New results on the independence number (Technical Report, Tel-Aviv University, 1979).
  4. S. Fajtlowicz, On the size of independent sets in graphs, in: 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. M.R. Garey, D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness (W.H. Freeman and Company, San Francisco, 1979).
  7. M.M. Halldorsson, J. Radhakrishnan, Greed is good: Approximating independent sets in sparse and bounded-degree graphs, Algorithmica 18 (1997) 145-163, doi: 10.1007/BF02523693.
  8. 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.
  9. J. Harant, A. Pruchnewski, M. Voigt, On dominating sets and independent sets of graphs, Combinatorics, Probability and Computing 8 (1999) 547-553, doi: 10.1017/S0963548399004034.
  10. J. Harant, I. Schiermeyer, On the independence number of a graph in terms of order and size, submitted.
  11. T.S. Motzkin, E.G. Straus, Maxima for graphs and a new proof of a theorem of Turan, Canad. J. Math. 17 (1965) 533-540, doi: 10.4153/CJM-1965-053-6.
  12. 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.
  13. S.M. Selkow, The independence number of graphs in terms of degrees, Discrete Math. 122 (1993) 343-348, doi: 10.1016/0012-365X(93)90307-F.
  14. 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.
  15. 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.
  16. 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.
  17. 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
2000/20/1
Export to PBN, Opens in new tab
Pages:
71-79
Main language of publication
English
Received
1999-02-08
Published
2000

DOI: 10.7151/dmgt.1107

Exact and natural sciences