Price of connectivity of graph parameters

Abstract

Vrcholové pokrytí grafu G je podmnožina vrcholů, která obsahuje alespoň jeden vrchol z každé hrany. Velikost nejmenšího vrcholového pokrytí se značí τ. Pokud navíc po vrcholech z vrcholového pokrytí chceme, aby indukovaly souvislý podgraf, pak se tato množina nazývá souvislé vrcholové pokrytí. Velikost minimálního vrcholového pokrytí se značí τc. Rozhodovací verze obou problému jsou NP-úplné. K lepšímu porozumění vztahů obou grafových invariantů autoři Cardinal and Levy zadefinovali cenu souvislosti grafu jako poměr čísel τc a τ. Není překvapující, že rozhod- nout, zda cena souvislosti pro daný graf je nejvýše rovna číslu t, je NP-těžký problém. Myšlenku ceny souvislosti je možno zobecnit i pro jiné grafové vlastnosti, jako například dominující množinu. Koncept ceny souvislosti už byl zkoumán v předchozí literatuře, z čehož některé články se soustředí na tzv. kritické grafy, což jsou grafy, kde cena souvislosti je ostře větší než cena souvislosti každého indukovaného podgrafu. Tato práce obsahuje rozšířený přehled současného vědění v oblasti ceny souvislosti. Dále se soustředí na strukturální vlastnosti kritických grafů a rozebírá možnou charak- terizaci grafů, ve kterých cena souvislosti za dominující množinu je nejvýše 7 3 pro každý indukovaný podgraf. 1

A vertex cover of a given graph is a vertex set including at least one endpoint from every edge. A vertex cover number τ is the size of a minimum vertex cover. If the vertices from a vertex cover are required to induce a connected subgraph, the resulting set is called a connected vertex cover. The corresponding parameter τc is called a connected vertex cover number. The decision versions of both problems are NP-complete. To better understand a relation between these two vertex cover numbers, Cardinal and Levy define the price of connectivity as a ratio between τc and τ. It is not surprising that determining whether the price of connectivity of a given graph is at most t is NP- hard. The notion of price of connectivity can be extended for more graph properties, such as for the dominating set. The price of connectivity has already been investigated in several papers, with some focusing on critical graphs whose price of connectivity is strictly greater than the price of connectivity of every induced subgraph. This thesis provides an overview of the current state of research into the price of connectivity. Moreover, we focus on the structural properties of critical graphs for the price of connectivity for vertex cover and discuss a possible characterization of graphs in which the price of connectivity for a...