Outerplanar obstructions for a feedback vertex set

详细信息    查看全文

• 作者：Juanjo Ru&eacute ; ^a ; ^{juanjo.rue@icmat.es} ; Konstantinos S. Stavropoulos^b ; ^{kstavro@math.uoa.gr} ; Dimitrios M. Thilikos^b ; ^{sedthilk@math.uoa.gr}
• 刊名：European Journal of Combinatorics
• 出版年：2012
• 出版时间：July, 2012
• 年：2012
• 卷：33
• 期：5
• 页码：948-968
• 全文大小：381 K

文摘

For , let be the class of graphs that contain vertices meeting all its cycles. The minor-obstruction set for is the set containing all minor-minimal graphs that do not belong to . We denote by the set of all outerplanar graphs in . In this paper, we provide a precise characterization of the class . Then, using singularity analysis over the counting series obtained with the Symbolic Method, we prove that where and ( is the smallest positive root of a quadratic equation).