Minor-obstructions for apex sub-unicyclic graphs

A. Leivaditis, A. Singh, G. Stamoulis, D. M. Thilikos, K. Tsatsanis, V. Velona

Research output: Contribution to journalArticlepeer-review

Abstract

A graph is sub-unicyclic if it contains at most one cycle. We also say that 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, 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 · k-2.5(6.278)k minor-obstructions.

Original languageEnglish (US)
Pages (from-to)903-910
Number of pages8
JournalActa Mathematica Universitatis Comenianae
Volume88
Issue number3
StatePublished - Sep 2 2019

Keywords

  • Graph minors
  • Obstruction set
  • Sub-unicyclic graphs

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

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

Cite this