# The Price of Connectivity for Vertex Cover and Dominating Set

## Eglantine Camby – Université libre de Bruxelles, Belgium

In this talk, we investigate the ratio of the connected version of a problem to the original problem in graphs, called the *Price of Connectivity* (PoC). Firstly, we study the PoC for Vertex Cover. For general graphs, this ratio is strictly bounded by 2. We prove that for every `\((P_5,C_5,C_4)\)`

-free graph the ratio equals 1. We prove also that for every `\((P_5,C_4)\)`

-free graph the ratio is bounded by `\(4/3\)`

and that for every `\((P_7,C_6, \Delta_1,\Delta_2)\)`

-free graph the ratio is bounded by `\(3/2\)`

, where `\(\Delta_1\)`

and `\(\Delta_2\)`

are two particular graphs. These results directly yields forbidden induced subgraphs characterizations of those graphs for which the PoC of every induced subgraph is bounded by `\(t\)`

, for `\(t \in \{1,4/3,3/2\}\)`

. Secondly, we study the PoC for Domination. The ratio of the connected domination number, `\(\gamma_c\)`

, and the domination number, `\(\gamma\)`

, is strictly bounded from above by 3. It was shown by Zverovich that for every connected `\((P_5,C_5)\)`

-free graph, `\(\gamma_c = \gamma\)`

. We investigate the interdependence of `\(\gamma\)`

and `\(\gamma_c\)`

in the class of `\((P_k,C_k)\)`

-free graphs, for `\(k \ge 6\)`

. We prove that for every connected `\((P_6,C_6)\)`

-free graph, `\(\gamma_c \le \gamma + 1\)`

holds, and there is a family of `\((P_6,C_6)\)`

-free graphs with arbitrarily large values of `\(\gamma\)`

attaining this bound. Moreover, for every connected `\((P_8,C_8)\)`

-free graph, `\(\gamma_c / \gamma \le 2\)`

, and there is a family of `\((P_7,C_7)\)`

-free graphs with arbitrarily large values of `\(\gamma\)`

attaining this bound. In the class of `\((P_9,C_9)\)`

-free graphs, the general bound `\(\gamma_c / \gamma\)`

< `\(3\)`

is asymptotically sharp.