The price of connectivity for feedback vertex set

Abstract: Let fvs

(G)

and cfvs(G) denote the cardinalities of a minimum feedback vertex set and a minimum connected feedback vertex set of a graph

G

, respectively. The price of connectivity for feedback vertex set (poc-fvs) for a class of graphs

c a l G

is defined as the maximum ratio

m b o x c f v s (G) / m b o x f v s (G)

over all connected graphs

G i n c a l G

. We study the poc-fvs for graph classes defined by a finite family

c a l H

of forbidden induced subgraphs. We characterize exactly those finite families

c a l H

for which the poc-fvs for

c a l H

-free graphs is upper bounded by a constant. Additionally, for the case where

| c a l H | = 1

, we determine exactly those graphs

H

for which there exists a constant

c_{H}

such that

m b o x c f v s (G) l e q m b o x f v s (G) + c_{H}

for every connected

H

-free graph

G

, as well as exactly those graphs

H

for which we can take

c_{H} = 0

.

Recommendations

Cites Work

Cited In (10)

This page was built for publication: The price of connectivity for feedback vertex set