14.11.2011 Lecturer: dr. Martin Milanič

Title:  Hereditary efficiently dominatable graphs

Abstract: An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the graph’s vertex set. It is NP-complete to determine whether a given graph contains an efficient dominating set. We study the class of hereditary
efficiently dominatable graphs, that is, graphs every induced subgraph of which contains an efficient dominating set. Based on a decomposition theorem for (bull, fork, C_4)-free graphs, we derive the forbidden induced subgraph characterization of hereditary efficiently dominatable graphs. We also present a polynomial time algorithm for finding an efficient dominating set (if one exists) in a class of graphs properly containing the class of hereditary efficiently dominatable graphs, by reducing the problem to the maximum weight independent set problem in claw-free graphs.

DOWNLOAD THE SLIDES FROM THE TALK: DOWNLOAD!