Minor-obstructions for apex sub-unicyclic graphs

DOI10.1016/J.DAM.2020.04.019zbMATH Open1443.05173arXiv1902.02231OpenAlexW3021599254WikidataQ114191505 ScholiaQ114191505MaRDI QIDQ777436FDOQ777436

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)

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.

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

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)

zbMATH Keywords

graph minorsobstruction setsub-unicyclc graphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
• Minor-obstructions for apex sub-unicyclic graphs
• Minor obstructions for apex-pseudoforests
• On strict brambles
• 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)