Mathematicae Graph Theory 22(2) (2002) 229-231
A NOTE ON DOMINATION IN BIPARTITE GRAPHS
Tobias Gerlach and Jochen Harant
Department of Mathematics
Technical University of Ilmenau
D-98684 Ilmenau, Germany
AbstractDOMINATING 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.
|||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.|
|||R. Diestel, Graph Theory (Springer-Verlag, New York, 2000).|
|||M.R. Garey and D.S. Johnson, Computers and Intractability (W.H. Freeman and Company, San Francisco, 1979).|
|||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