Abstract (Vadim Zverovich)

For a graph G, a subset of vertices X is called independent if no vertices in X are adjacent; X is called dominating if any vertex not in X is adjacent to some vertex of X. The domination number gamma(G) is the minimum cardinality taken over all dominating sets of G, and the independent domination number i(G) is the minimum cardinality taken over all maximal independent sets of vertices of G. A graph G is called domination perfect if gamma(H)=i(H), for every induced subgraph H of G. There are many results giving a partial characterization of domination perfect graphs. In this talk we present a finite induced subgraph characterization of the entire class of domination perfect graphs. The list of forbidden subgraphs in the characterization consists of 17 minimal domination imperfect graphs. Moreover, the dominating set and independent dominating set problems are shown to be both NP-complete on some classes of graphs.

Last modified: November 28, 1995.

Kim Skak Larsen (kslarsen@imada.sdu.dk)