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

Main Article Content

Alexandros Leivaditis Alexandros Singh Giannos Stamoulis Dimitrios M. Thilikos Konstantinos Tsatsanis Vasiliki Velona


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.

Article Details

How to Cite
Leivaditis, A., Singh, A., Stamoulis, G., Thilikos, D., Tsatsanis, K., & Velona, V. (2019). Minor-obstructions for apex sub-unicyclic graphs. Acta Mathematica Universitatis Comenianae, 88(3), 903-910. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1248/775