Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

The price of connectivity for cycle transversals.

Hartinger, T.R. and Johnson, M. and Milanič, M. and Paulusma, D. (2016) 'The price of connectivity for cycle transversals.', European journal of combinatorics., 58 . pp. 203-224.

Abstract

For a family of graphs F, an F-transversal of a graph G is a subset S⊆V(G) that intersects every subset of V(G) that induces a subgraph isomorphic to a graph in F. Let tF(G) be the minimum size of an F-transversal of G, and View the MathML source be the minimum size of an F-transversal of G that induces a connected graph. For a class of connected graphs G, we say that the price of connectivity of F-transversals is multiplicative if, for all G∈G, View the MathML source is bounded by a constant, and additive if View the MathML source is bounded by a constant. The price of connectivity is identical if tF(G) and View the MathML source are always equal and unbounded if View the MathML source cannot be bounded in terms of tF(G). We study classes of graphs characterized by one forbidden induced subgraph H and F-transversals where F contains an infinite number of cycles and, possibly, also one or more anticycles or short paths. We determine exactly those classes of connected H-free graphs where the price of connectivity of these F-transversals is unbounded, multiplicative, additive, or identical. In particular, our tetrachotomies extend known results for the case when F is the family of all cycles.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
(471Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1016/j.ejc.2016.06.003
Publisher statement:© 2016 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Date accepted:05 June 2016
Date deposited:30 June 2016
Date of first online publication:29 June 2016
Date first made open access:29 December 2016

Save or Share this output

Export:
Export
Look up in GoogleScholar