# On domination in graphs

Discussiones Mathematicae Graph Theory (2005)

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

## Access Full Article

top## Abstract

top## How to cite

topFrank 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] Y. Caro, New results on the independence number (Technical Report, Tel-Aviv University, 1979).
- [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] R. Diestel, Graph Theory, Graduate Texts in Mathematics (Springer, 1997).
- [4] N. Alon, J.H. Spencer and P. Erdös, The Probabilistic Method (John Wiley and Sons, Inc. 1992), page 6.
- [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] 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] 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] 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] 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).

## Citations in EuDML Documents

top## NotesEmbed ?

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