PDF
Discussiones
Mathematicae Graph Theory 22(2) (2002) 229-231
DOI: https://doi.org/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
Close