Group for Research in Decision Analysis

The price of connectivity for dominating set and further extensions with GraphsInGraphs

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 the Domination problem. The ratio of the connected domination number, \(\gamma_c\) , and the domination number, \(\gamma\), is strictly bounded from above by 3. We consider the computational aspect for computing the PoC and we extend some structural results, for instance, it was shown by Zverovich that for every connected \(P_5, C_5\)-free graph, \(\gamma = \gamma_c\), and the class of \((P_5, C_5)\)-free graph is the largest satisfying this equality for all induced subgraphs. We prove that being a connected \((P_6, C_6)\)-free graph is equivalent to satisfy \(PoC(H) \leq \frac{3}{2}\) for all induced subgraphs \(H\). Moreover, for every connected \((P_8, C_8)\)-free graph, \(\frac{\gamma_c}{\gamma} \leq 2\). However, this class is not the largest one.

Secondly, to find the list of forbidden induced subgraphs, we introduce the notion of critical graphs: a graph \(G\) such that \(PoC(H)<PoC(G)\) for every induced subgraph \(H\). In order to characterize these graphs, we develop a new system called GraphsInGraphs (GIG). The system makes the links between a graph and theirs induced subgraphs. Maybe you have already an application for our system? It is welcome!

This is joint work with Oliver Schaudt and Gilles Caporossi.


This seminar is only open to students of GERAD.
We would highly appreciate if you could confirm your attendance with your full name. Pizza and non alcoholic beverages will be available; you can also bring your own lunch.