Outerplanar Obstructions for the Feedback Vertex Set

Juanjo Rué; Konstantinos S. Stavropoulos; Dimitrios M. Thilikos

doi:10.1016/j.endm.2009.07.028

Outerplanar Obstructions for the Feedback Vertex Set

Juanjo Rué, Konstantinos S. Stavropoulos, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

For k ≥ 1, let F_k be the class containing every graph that contains k vertices meeting all its cycles. The minor-obstruction set for F_k is the set obs (F_k) containing all minor-minimal graph that does not belong to F_k. We denote by Y_k the set of all outerplanar graphs in obs (F_k). In this paper, we provide a precise characterization of the class Y_k. Then, using the symbolic method, we prove that | Y_k | ∼ α ṡ k^{- 5 / 2} ṡ ρ^{- k} where α {approaches the limit} 0.02602193 and ρ^{- 1} {approaches the limit} 14.49381704.

Original language	English (US)
Pages (from-to)	167-171
Number of pages	5
Journal	Electronic Notes in Discrete Mathematics
Volume	34
DOIs	https://doi.org/10.1016/j.endm.2009.07.028
State	Published - Aug 1 2009

Keywords

feedback vertex set
graph enumeration
Graph minors
obstructions
outerplanar graphs
singularity analysis

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.endm.2009.07.028

Cite this

@article{9b61f42586184e50862e86749172471e,

title = "Outerplanar Obstructions for the Feedback Vertex Set",

abstract = "For k ≥ 1, let Fk be the class containing every graph that contains k vertices meeting all its cycles. The minor-obstruction set for Fk is the set obs (Fk) containing all minor-minimal graph that does not belong to Fk. We denote by Yk the set of all outerplanar graphs in obs (Fk). In this paper, we provide a precise characterization of the class Yk. Then, using the symbolic method, we prove that | Yk | ∼ α ṡ k- 5 / 2 ṡ ρ- k where α {approaches the limit} 0.02602193 and ρ- 1 {approaches the limit} 14.49381704.",

keywords = "feedback vertex set, graph enumeration, Graph minors, obstructions, outerplanar graphs, singularity analysis",

author = "Juanjo Ru{\'e} and Stavropoulos, {Konstantinos S.} and Thilikos, {Dimitrios M.}",

year = "2009",

month = aug,

day = "1",

doi = "10.1016/j.endm.2009.07.028",

language = "English (US)",

volume = "34",

pages = "167--171",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - Outerplanar Obstructions for the Feedback Vertex Set

AU - Rué, Juanjo

AU - Stavropoulos, Konstantinos S.

AU - Thilikos, Dimitrios M.

PY - 2009/8/1

Y1 - 2009/8/1

N2 - For k ≥ 1, let Fk be the class containing every graph that contains k vertices meeting all its cycles. The minor-obstruction set for Fk is the set obs (Fk) containing all minor-minimal graph that does not belong to Fk. We denote by Yk the set of all outerplanar graphs in obs (Fk). In this paper, we provide a precise characterization of the class Yk. Then, using the symbolic method, we prove that | Yk | ∼ α ṡ k- 5 / 2 ṡ ρ- k where α {approaches the limit} 0.02602193 and ρ- 1 {approaches the limit} 14.49381704.

AB - For k ≥ 1, let Fk be the class containing every graph that contains k vertices meeting all its cycles. The minor-obstruction set for Fk is the set obs (Fk) containing all minor-minimal graph that does not belong to Fk. We denote by Yk the set of all outerplanar graphs in obs (Fk). In this paper, we provide a precise characterization of the class Yk. Then, using the symbolic method, we prove that | Yk | ∼ α ṡ k- 5 / 2 ṡ ρ- k where α {approaches the limit} 0.02602193 and ρ- 1 {approaches the limit} 14.49381704.

KW - feedback vertex set

KW - graph enumeration

KW - Graph minors

KW - obstructions

KW - outerplanar graphs

KW - singularity analysis

UR - http://www.scopus.com/inward/record.url?scp=67651165184&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67651165184&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2009.07.028

DO - 10.1016/j.endm.2009.07.028

M3 - Article

AN - SCOPUS:67651165184

SN - 1571-0653

VL - 34

SP - 167

EP - 171

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Outerplanar Obstructions for the Feedback Vertex Set

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this