A note on domination in bipartite graphs
Tobias Gerlach ; Jochen Harant
Discussiones Mathematicae Graph Theory, Tome 22 (2002), p. 229-231 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2002-01-01
EUDML-ID : urn:eudml:doc:270363 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1171,
     author = {Tobias Gerlach and Jochen Harant},
     title = {A note on domination in bipartite graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {22},
     year = {2002},
     pages = {229-231},
     zbl = {1028.05075},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1171}
}

Tobias Gerlach; Jochen Harant. A note on domination in bipartite graphs. Discussiones Mathematicae Graph Theory, Tome 22 (2002) pp. 229-231. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1171/

[000] [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. | Zbl 0576.05054

[001] [2] R. Diestel, Graph Theory (Springer-Verlag, New York, 2000).

[002] [3] M.R. Garey and D.S. Johnson, Computers and Intractability (W.H. Freeman and Company, San Francisco, 1979).

[003] [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. | Zbl 0959.05080