Minor-obstructions for apex sub-unicyclic graphs

Discrete Applied Mathematics, vol. 284, pp. 538–555

Abstract

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.

Authors 6

1. Alexandros Leivaditis Aachen Mathematical Institute

   Leiden University · National and Kapodistrian University of Athens

   Affiliation as printed

   Department of Mathematics, National and Kapodistrian University of Athens, Athens, Greece

   Mathematical Institute, Universiteit Leiden, The Netherlands

2. Alexandros Singh

   Centre National de la Recherche Scientifique · National and Kapodistrian University of Athens · Université Sorbonne Paris Nord · Laboratoire d'Informatique de Paris-Nord

   Affiliation as printed

   Inter-university Postgraduate Programme “Algorithms, Logic, and Discrete Mathematics” (ALMA), Greece

   Université Sorbonne Paris Nord, Laboratoire d’Informatique de Paris Nord, CNRS, Villetaneuse, France

   national & kapodistrian university of athens

3. Giannos Stamoulis

   National and Kapodistrian University of Athens

   Affiliation as printed

   Inter-university Postgraduate Programme “Algorithms, Logic, and Discrete Mathematics” (ALMA), Greece

   national & kapodistrian university of athens

4. Dimitrios M. Thilikos

   Centre National de la Recherche Scientifique · Université de Montpellier · Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier

   Affiliation as printed

   AlGCo project-team, LIRMM, CNRS, Université de Montpellier, Montpellier, France

5. Konstantinos Tsatsanis
   Affiliation as printed

   Inter-university Postgraduate Programme “Algorithms, Logic, and Discrete Mathematics” (ALMA), Greece

6. Vasiliki Velona corresponding

   Universitat Pompeu Fabra · Universitat Politècnica de Catalunya

   Affiliation as printed

   Department of Economics, Universitat Pompeu Fabra, Barcelona, Spain

   Department of Mathematics, Universitat Politècnica de Catalunya, Barcelona, Spain

   Pompeu Fabra Univ