Clustering and domination in perfect graphs

D. G. Corneil, Y. Perl

Research output: Contribution to journalArticlepeer-review

153 Scopus citations

Abstract

A k-cluster in a graph is an induced subgraph on k vertices which maximizes the number of edges. Both the k-cluster problem and the k-dominating set problem are NP-complete for graphs in general. In this paper we investigate the complexity status of these problems on various sub-classes of perfect graphs. In particular, we examine comparability graphs, chordal graphs, bipartite graphs, split graphs, cographs and κ-trees. For example, it is shown that the k-cluster problem is NP-complete for both bipartite and chordal graphs and the independent k-dominating set problem is NP-complete for bipartite graphs. Furthermore, where the k-cluster problem is polynomial we study the weighted and connected versions as well. Similarly we also look at the minimum k-dominating set problem on families which have polynomial k-dominating set algorithms.

Original languageEnglish (US)
Pages (from-to)27-39
Number of pages13
JournalDiscrete Applied Mathematics
Volume9
Issue number1
DOIs
StatePublished - Sep 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Clustering and domination in perfect graphs'. Together they form a unique fingerprint.

Cite this