Dominating sets for split and bipartite graphs

https://doi.org/10.1016/0020-0190(84)90126-1Get rights and content

Abstract

A dominating set of an undirected graph G is a set D of nodes such that every node of G either is in D or is adjacent to some node of D. It is shown that the problem of finding a minimum cardinality dominating set is NP-complete for split graphs (a subclass of chordal graphs) and bipartite graphs.

References (19)

There are more references available in the full text version of this article.

Cited by (0)

This research was financially supported by a Grant from the Ministero della Pubblica Istruzione of Italy.

View full text