Robust connectivity of graphs on surfaces

DOI10.1137/21M1417077zbMATH Open1492.05077arXiv2104.12030OpenAlexW4283011735MaRDI QIDQ5084099FDOQ5084099

Authors: Peter Bradshaw, Tomáš Masařík, Jana Novotná, Ladislav Stacho 

Publication date: 23 June 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Let $Lambda(T)$ denote the set of leaves in a tree $T$. One natural problem is to look for a spanning tree $T$ of a given graph $G$ such that $Lambda(T)$ is as large as possible. This problem is called maximum leaf number, and it is a well-known NP-hard problem. Throughout recent decades, this problem has received considerable attention, ranging from pure graph theoretic questions to practical problems related to the construction of wireless networks. Recently, a similar but stronger notion was defined by Bradshaw, Masav{r}'ik, and Stacho [Flexible List Colorings in Graphs with Special Degeneracy Conditions, ISAAC 2020]. They introduced a new invariant for a graph $G$, called the robust connectivity and written $kapp{a}_{h}o(G)$, defined as the minimum value $frac|RcapLambda(T)||R|$ taken over all nonempty subsets $RsubseteqV(G)$, where $T=T(R)$ is a spanning tree on $G$ chosen to maximize $|RcapLambda(T)|$. Large robust connectivity was originally used to show flexible choosability in non-regular graphs. In this paper, we investigate some interesting properties of robust connectivity for graphs embedded in surfaces. We prove a tight asymptotic bound of $Omega(gamm{a}^{-frac1r})$ for the robust connectivity of $r$-connected graphs of Euler genus $gamma$. Moreover, we give a surprising connection between the robust connectivity of graphs with an edge-maximal embedding in a surface and the surface connectivity of that surface, which describes to what extent large induced subgraphs of embedded graphs can be cut out from the surface without splitting the surface into multiple parts. For planar graphs, this connection provides an equivalent formulation of a long-standing conjecture of Albertson and Berman [A conjecture on planar graphs, 1979], which states that every planar graph on $n$ vertices contains an induced forest of size at least $n/2$.

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

Recommendations

• Tree robustness of a graph
• Spanning Trees with Bounded Maximum Degrees of Graphs on Surfaces
• On the connectivity of graphs embedded in surfaces. II
• The connectivities of leaf graphs of 2-connected graphs
• 2-connected spanning subgraphs with low maximum degree in locally planar graphs

zbMATH Keywords

graphs on surfacesAlbertson-Berman conjecturerobust connectivity

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Spanning trees in graphs of minimum degree 4 or 5
• On acyclic colorings of planar graphs
• Graphs on surfaces
• Spanning Trees with Many Leaves
• Title not available (Why is that?)
• Max-leaves spanning tree is APX-hard for cubic graphs
• An exact algorithm for the maximum leaf spanning tree problem
• Minimum feedback vertex set and acyclic coloring.
• Large induced forests in triangle-free planar graphs
• Title not available (Why is that?)
• Constructing full spanning trees for cubic graphs
• Solving connected dominating set faster than \(2^n\)
• Spanning trees with many leaves in cubic graphs
• The complexity ecology of parameters: An illustration using bounded max leaf number
• Homeomorphically irreducible spanning trees in locally connected graphs
• Graphs with homeomorphically irreducible spanning trees
• A 3/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs
• Connected dominating set. Theory and applications
• Large induced forests in planar graphs with girth 4
• Large induced forests in graphs
• Minimum size of feedback vertex sets of planar graphs of girth at least five
• A lower bound on the order of the largest induced linear forest in triangle-free planar graphs
• Title not available (Why is that?)
• Maximum and minimum toughness of graphs of small genus
• Edge-maximal graphs on surfaces
• Robust randomized matchings
• Edge‐maximal graphs on orientable and some nonorientable surfaces
• Below all subsets for minimal connected dominating set
• The genus of complete 3-uniform hypergraphs
• Flexible List Colorings in Graphs with Special Degeneracy Conditions

This page was built for publication: Robust connectivity of graphs on surfaces

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