DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 22(2) (2002) 229-231
DOI: 10.7151/dmgt.1171

A NOTE ON DOMINATION IN BIPARTITE GRAPHS

Tobias Gerlach and Jochen Harant

Department of Mathematics
Technical University of Ilmenau
D-98684 Ilmenau, Germany

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.

Keywords: bipartite graph, domination.

2000 Mathematics Subject Classification: 05C35.

References

[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.
[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.

Received 24 August 2000