On domination in graphs

Frank Göring; Jochen Harant

Discussiones Mathematicae Graph Theory (2005)

  • Volume: 25, Issue: 1-2, page 7-12
  • ISSN: 2083-5892

Abstract

top
For a finite undirected graph G on n vertices two continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the domination number γ of G. An efficient approximation method is developed and known upper bounds on γ are slightly improved.

How to cite

top

Frank Göring, and Jochen Harant. "On domination in graphs." Discussiones Mathematicae Graph Theory 25.1-2 (2005): 7-12. <http://eudml.org/doc/270234>.

@article{FrankGöring2005,
abstract = {For a finite undirected graph G on n vertices two continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the domination number γ of G. An efficient approximation method is developed and known upper bounds on γ are slightly improved.},
author = {Frank Göring, Jochen Harant},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph; domination; optimization problems; approximation method},
language = {eng},
number = {1-2},
pages = {7-12},
title = {On domination in graphs},
url = {http://eudml.org/doc/270234},
volume = {25},
year = {2005},
}

TY - JOUR
AU - Frank Göring
AU - Jochen Harant
TI - On domination in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 1-2
SP - 7
EP - 12
AB - For a finite undirected graph G on n vertices two continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the domination number γ of G. An efficient approximation method is developed and known upper bounds on γ are slightly improved.
LA - eng
KW - graph; domination; optimization problems; approximation method
UR - http://eudml.org/doc/270234
ER -

References

top
  1. [1] Y. Caro, New results on the independence number (Technical Report, Tel-Aviv University, 1979). 
  2. [2] Y. Caro and Zs. Tuza, Improved lower bounds on k-independence, J. Graph Theory 15 (1991) 99-107, doi: 10.1002/jgt.3190150110. 
  3. [3] R. Diestel, Graph Theory, Graduate Texts in Mathematics (Springer, 1997). 
  4. [4] N. Alon, J.H. Spencer and P. Erdös, The Probabilistic Method (John Wiley and Sons, Inc. 1992), page 6. 
  5. [5] M.R. Garey and D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness (W.H. Freeman and Company, San Francisco, 1979). Zbl0411.68039
  6. [6] J. Harant, Some news about the independence number of a graph, Discuss. Math. Graph Theory 20 (2000) 71-79, doi: 10.7151/dmgt.1107. Zbl0971.05058
  7. [7] J. Harant, A. Pruchnewski and M. Voigt, On dominating sets and independent sets of graphs, Combinatorics, Probability and Computing 8 (1999) 547-553, doi: 10.1017/S0963548399004034. Zbl0959.05080
  8. [8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, N.Y., 1998), page 52. Zbl0890.05002
  9. [9] 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.