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

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

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 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.


Ce séminaire s'adresse seulement aux étudiants du GERAD.
Nous vous remercions de confirmer votre présence en indiquant votre nom complet. Des pizzas et des breuvages seront servis aux participants ou vous pouvez apporter votre lunch.