# A note on domination in bipartite graphs

Discussiones Mathematicae Graph Theory (2002)

- Volume: 22, Issue: 2, page 229-231
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topTobias Gerlach, and Jochen Harant. "A note on domination in bipartite graphs." Discussiones Mathematicae Graph Theory 22.2 (2002): 229-231. <http://eudml.org/doc/270363>.

@article{TobiasGerlach2002,

abstract = {DOMINATING SET remains NP-complete even when instances are restricted to bipartite graphs, however, in this case VERTEX COVER is solvable in polynomial time. Consequences to VECTOR DOMINATING SET as a generalization of both are discussed.},

author = {Tobias Gerlach, Jochen Harant},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {bipartite graph; domination; vector dominating set; NP-complete problem},

language = {eng},

number = {2},

pages = {229-231},

title = {A note on domination in bipartite graphs},

url = {http://eudml.org/doc/270363},

volume = {22},

year = {2002},

}

TY - JOUR

AU - Tobias Gerlach

AU - Jochen Harant

TI - A note on domination in bipartite graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2002

VL - 22

IS - 2

SP - 229

EP - 231

AB - DOMINATING SET remains NP-complete even when instances are restricted to bipartite graphs, however, in this case VERTEX COVER is solvable in polynomial time. Consequences to VECTOR DOMINATING SET as a generalization of both are discussed.

LA - eng

KW - bipartite graph; domination; vector dominating set; NP-complete problem

UR - http://eudml.org/doc/270363

ER -

## References

top- [1] G.J. Chang and G.L. Nemhauser, The k-domination and k-stability problems in sun-free chordal graphs, SIAM J. Algebraic Discrete Methods 5 (1984) 332-345, doi: 10.1137/0605034. Zbl0576.05054
- [2] R. Diestel, Graph Theory (Springer-Verlag, New York, 2000).
- [3] M.R. Garey and D.S. Johnson, Computers and Intractability (W.H. Freeman and Company, San Francisco, 1979).
- [4] 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

## NotesEmbed ?

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