Minor-obstructions for apex sub-unicyclic graphs Obstructions for Apex Sub-unicyclic Graphs

Abstract

A graph is {\em sub-unicyclic} if it contains at most one cycle. We also say that a graph $G$ is  {\em $k$-apex sub-unicyclic} if it can become sub-unicyclic by removing $k$ of its vertices.  We identify 29 graphs that are the minor-obstructions of the class of {$1$-apex} sub-unicyclic graphs,  i.e., the set of all minor minimal graphs that do not belong in this class.   For bigger values of $k$, we give an exact structural characterization of all the cactus graphs that are minor-obstructions  of {$k$-apex} sub-unicyclic graphs and we enumerate them. This implies that, for every $k$,   the class of $k$-apex sub-unicyclic graphs has  at least $0.34\cdot k^{-2.5}(6.278)^{k}$ minor-obstructions.