Some news about the independence number of a graph

Jochen Harant

Discussiones Mathematicae Graph Theory (2000)

  • Volume: 20, Issue: 1, page 71-79
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Jochen Harant. "Some news about the independence number of a graph." Discussiones Mathematicae Graph Theory 20.1 (2000): 71-79. <http://eudml.org/doc/270402>.

@article{JochenHarant2000,
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.},
author = {Jochen Harant},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph; independence; independence number},
language = {eng},
number = {1},
pages = {71-79},
title = {Some news about the independence number of a graph},
url = {http://eudml.org/doc/270402},
volume = {20},
year = {2000},
}

TY - JOUR
AU - Jochen Harant
TI - Some news about the independence number of a graph
JO - Discussiones Mathematicae Graph Theory
PY - 2000
VL - 20
IS - 1
SP - 71
EP - 79
AB - 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.
LA - eng
KW - graph; independence; independence number
UR - http://eudml.org/doc/270402
ER -

References

top
  1. [1] E. Bertram, P. Horak, Lower bounds on the independence number, Geombinatorics, (V) 3 (1996) 93-98. Zbl0972.05024
  2. [2] R. Boppana, M.M. Halldorsson, Approximating maximum independent sets by excluding subgraphs, BIT 32 (1992) 180-196, doi: 10.1007/BF01994876. Zbl0761.68044
  3. [3] Y. Caro, New results on the independence number (Technical Report, Tel-Aviv University, 1979). 
  4. [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. Zbl0434.05044
  5. [5] S. Fajtlowicz, Independence, clique size and maximum degree, Combinatorica 4 (1984) 35-38, doi: 10.1007/BF02579154. Zbl0576.05025
  6. [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). Zbl0411.68039
  7. [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. Zbl0866.68077
  8. [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. Zbl0958.05067
  9. [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. Zbl0959.05080
  10. [10] J. Harant, I. Schiermeyer, On the independence number of a graph in terms of order and size, submitted. Zbl1030.05091
  11. [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. Zbl0129.39902
  12. [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. Zbl0755.05055
  13. [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. Zbl0791.05062
  14. [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. Zbl0810.05039
  15. [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. Zbl0516.05053
  16. [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. Zbl0753.05074
  17. [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). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.