Robust Connectivity of Graphs on Surfaces
From MaRDI portal
Publication:5084099
DOI10.1137/21M1417077zbMath1492.05077arXiv2104.12030OpenAlexW4283011735MaRDI QIDQ5084099
Peter Bradshaw, Ladislav Stacho, Jana Novotná, Tomáš Masařík
Publication date: 23 June 2022
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2104.12030
Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Max-leaves spanning tree is APX-hard for cubic graphs
- Connected dominating set. Theory and applications
- An exact algorithm for the maximum leaf spanning tree problem
- Minimum size of feedback vertex sets of planar graphs of girth at least five
- The complexity ecology of parameters: An illustration using bounded max leaf number
- Solving connected dominating set faster than \(2^n\)
- Constructing full spanning trees for cubic graphs
- Spanning trees in graphs of minimum degree 4 or 5
- On acyclic colorings of planar graphs
- Maximum and minimum toughness of graphs of small genus
- Large induced forests in planar graphs with girth 4
- A lower bound on the order of the largest induced linear forest in triangle-free planar graphs
- Minimum feedback vertex set and acyclic coloring.
- The genus of complete 3-uniform hypergraphs
- Large induced forests in triangle-free planar graphs
- Homeomorphically Irreducible Spanning Trees in Locally Connected Graphs
- Spanning trees with many leaves in cubic graphs
- A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
- Spanning Trees with Many Leaves
- Edge-Maximal Graphs on Surfaces
- Below All Subsets for Minimal Connected Dominating Set
- Graphs with homeomorphically irreducible spanning trees
- Large Induced Forests in Graphs
- Robust Randomized Matchings
- Edge‐maximal graphs on orientable and some nonorientable surfaces
- Flexible List Colorings in Graphs with Special Degeneracy Conditions
