Abstract: We study a graph parameter called the Price of Connectivity for Vertex Cover (PoC). It was recently introduced by Cardinal et al. and is defined as the ratio of the minimum size of a connected vertex cover and the minimum size of a vertex cover.We prove some structural results for the PoC. These results concern PoC-critical, PoC-perfect and PoC-near-perfect graphs.

Joint work with E. Camby, J. Cardinal and S. Fiorini.

 

Slides from the talk are available here: DOWNLOAD!