Graphs and Matroids Seminar

Title: The price of connectivity for domination

Abstract: The price of connectivity for dominating set in a graph G is the ratio between the minimum sizes of a connected dominating set and a dominating set of G. It is always at most three, and Zverovich characterized the class of graphs such that this ratio equals one. In this talk, we give a proof of a conjecture of Camby and Schaudt by characterizing the class of graphs with price of connectivity at most two. This is joint work with Marthe Bonamy, Nicolas Bousquet and Tereza Klimošová.