Groupe d’études et de recherche en analyse des décisions

The Price of Connectivity for Vertex Cover and Dominating Set

Eglantine Camby Université libre de Bruxelles, Belgique

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.