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 language | English (US) |
---|---|
Pages (from-to) | 903-910 |
Number of pages | 8 |
Journal | Acta Mathematica Universitatis Comenianae |
Volume | 88 |
Issue number | 3 |
State | Published - Sep 2 2019 |
Keywords
- Graph minors
- Obstruction set
- Sub-unicyclic graphs
ASJC Scopus subject areas
- General Mathematics