Enumeration of Cactus Minor-Obstructions for k-Apex Submonocyclic Graphs

Submitted by admin on Mon, 17/12/2018 - 18:20
Alexandros Singh
Date of Defense
Three-member Committee
Christos A. Athanasiadis
Dimitrios M. Thilikos (Advisor)
Dimitris Zoros

A graph is subunicyclic if it contains at most one cycle. A graph is k-apex subunicyclic if it can be made subunicyclic by removing k of its vertices. The purpose of this talk is to present a structural characterisation and an enumeration of the subset of obstructions for k-apex subunicyclicity consisting of cacti. To achieve the characterisation and enumeration of these cactus-obstructions, we made use of techniques and results from (structural) graph theory, enumerative and analytic combinatorics, and the theory of combinatorial species.