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
topHow 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 ?
topYou 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.