Minor-obstructions for apex sub-unicyclic graphs

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

Research output: Contribution to journalArticlepeer-review


A graph is sub-unicyclic if it contains at most one cycle. A graph G is 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. 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 k big enough, the class of k-apex sub-unicyclic graphs has at least 0.33⋅k−2.5(6.278)k+1 minor-obstructions.

Original languageEnglish (US)
Pages (from-to)538-555
Number of pages18
JournalDiscrete Applied Mathematics
StatePublished - Sep 30 2020


  • Graph minors
  • Obstruction set
  • Sub-unicyclc graphs

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Minor-obstructions for apex sub-unicyclic graphs'. Together they form a unique fingerprint.

Cite this