Download PDF - A note on domination in bipartite graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

A note on domination in bipartite graphs

Authors 1, 1

Affiliations

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

ENG
bipartite graph, domination

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2002/22/2
Export to PBN, Opens in new tab
Pages:
229-231
Main language of publication
English
Received
2000-08-24
Published
2002

DOI: 10.7151/dmgt.1171

Exact and natural sciences