Rooted minors and locally spanning subgraphs

DOI10.1002/JGT.23012MaRDI QIDQ6143382zbMATH OpenOpenAlexFDO

Authors T. Böhme, Jochen Harant, Matthias Kriesell, S. Mohr, Jens M. Schmidt

Publication date 24 January 2024

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

connectednessminorrooted minorspanning subgraph

Mathematics Subject Classification ID

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

Abstract: Results on the existence of various types of spanning subgraphs of graphs are milestones in structural graph theory and have been diversified in several directions. In the present paper, we consider "local" versions of such statements. In 1966, for instance, D. W. Barnette proved that a $3$-connected planar graph contains a spanning tree of maximum degree at most $3$. A local translation of this statement is that if $G$ is a planar graph, $X$ is a subset of specified vertices of $G$ such that $X$ cannot be separated in $G$ by removing $2$ or fewer vertices of $G$, then $G$ has a tree of maximum degree at most $3$ containing all vertices of $X$. Our results constitute a general machinery for strengthening statements about $k$-connected graphs (for $1leqkleq4$) to locally spanning versions, i.e. subgraphs containing a set $XsubseteqV(G)$ of a (not necessarily planar) graph $G$ in which only $X$ has high connectedness. Given a graph $G$ and $XsubseteqV(G)$, we say $M$ is a minor of $G$ rooted at $X$, if $M$ is a minor of $G$ such that each bag of $M$ contains at most one vertex of $X$ and $X$ is a subset of the union of all bags. We show that $G$ has a highly connected minor rooted at $X$ if $XsubseteqV(G)$ cannot be separated in $G$ by removing a few vertices of $G$. Combining these investigations and the theory of Tutte paths in the planar case yields to locally spanning versions of six well-known results about degree-bounded trees, hamiltonian paths and cycles, and $2$-connected subgraphs of graphs.

Recommendations

• scientific article; zbMATH DE number 3487529
• scientific article; zbMATH DE number 3080938
• scientific article; zbMATH DE number 3407754
• Eine Bemerkung zum Satz von Vitali über Konvergenz von Funktionenfolgen: Dem stets hilftsbereiten Herrn Kollegen H. L. Schmid, gewidmet
• scientific article; zbMATH DE number 1839786
• Holomorphic mappings of complex manifolds
• scientific article; zbMATH DE number 5593209
• On \(\varepsilon\)-representations
• scientific article; zbMATH DE number 3148394

Cites work

• 2-connected spanning subgraphs of planar 3-connected graphs
• 2‐connected coverings of bounded degree in 3‐connected graphs
• 4-connected projective planar graphs are Hamiltonian
• A theorem on paths in planar graphs
• A Theorem on Planar Graphs
• Graph theory
• Hamilton paths in toroidal graphs
• Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs
• scientific article; zbMATH DE number 1002024 (Why is no real title available?)
• scientific article; zbMATH DE number 1156578 (Why is no real title available?)
• Menger's theorem
• Spanning trees in 3-connected \(K_{3,t}\)-minor-free graphs
• Spanning trees: A survey
• Trees and Co-trees with Bounded Degrees in Planar 3-connected Graphs
• Trees in Polyhedral Graphs

Cited in

(3)

• Toward Grünbaum's conjecture
• Toward Grünbaum's conjecture bounding vertices of degree 4
• A polynomial time algorithm for Steiner tree when terminals avoid a rooted K₄-minor

This page was built for publication: Rooted minors and locally spanning subgraphs

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