Minor-obstructions for apex sub-unicyclic graphs

DOI10.1016/J.DAM.2020.04.019MaRDI QIDQ777436zbMATH OpenOpenAlexWikidataFDO

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

Publication date 7 July 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.02231

zbMATH Keywords

graph minorsobstruction setsub-unicyclc graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph minors (05C83)

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.34cdot{k}^{-2.5}(6.278{)}^k$ minor-obstructions.

Recommendations

• \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
• Minor obstructions for apex-pseudoforests
• All minor-minimal apex obstructions with connectivity two
• Six variations on a theme: almost planar graphs
• Unified extremal results for \(k\)-apex unicyclic graphs (trees)

Cites work

• scientific article; zbMATH DE number 986989 (Why is no real title available?)
• scientific article; zbMATH DE number 5764786 (Why is no real title available?)
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 1111371 (Why is no real title available?)
• scientific article; zbMATH DE number 1543076 (Why is no real title available?)
• scientific article; zbMATH DE number 867627 (Why is no real title available?)
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
• Analytic combinatorics
• Asymptotic enumeration of non-crossing partitions on surfaces
• Enumeration and asymptotic properties of unlabeled outerplanar graphs
• Excluded-minor characterization of apex-outerplanar graphs
• Forbidden graphs for tree-depth
• Forbidden minors to graphs with small feedback sets
• Graph minors. XX: Wagner's conjecture
• Minor‐order obstructions for the graphs of vertex cover 6
• More forbidden minors for wye-delta-wye reducibility
• On computing graph minor obstruction sets
• Outerplanar obstructions for a feedback vertex set
• Outerplanar obstructions for matroid pathwidth
• Six variations on a theme: almost planar graphs

Cited in

(6)

• Minor obstructions for apex-pseudoforests
• On strict brambles
• \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
• Minor-obstructions for apex sub-unicyclic graphs
• Almost square permutations are typically square
• \(\mathcal{P}\)-apex graphs

This page was built for publication: Minor-obstructions for apex sub-unicyclic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q777436)