Rooted minors and locally spanning subgraphs

T Böhme, J Harant, M Kriesell, S Mohr… - Journal of Graph …, 2024 - Wiley Online Library
T Böhme, J Harant, M Kriesell, S Mohr, JM Schmidt
Journal of Graph Theory, 2024Wiley Online Library
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, DW 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 GG is a planar graph, XX is a subset of specified
vertices of GG such that XX cannot be separated in GG by removing two or fewer vertices of …
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 $G$ is a planar graph, X $X$ is a subset of specified vertices of G $G$ such that X $X$ cannot be separated in G $G$ by removing two or fewer vertices of G $G$, then G $G$ has a tree of maximum degree at most 3 containing all vertices of X $X$. Our results constitute a general machinery for strengthening statements about k $k$‐connected graphs (for 1 ≤ k ≤ 4 $1\le k\le 4$) to locally spanning versions, that is, subgraphs containing a set X ⊆ V( G ) $X\subseteq V(G)$ of a (not necessarily planar) graph G $G$ in which only X $X$ has high connectedness. Given a graph G $G$ and X ⊆ V( G ) $X\subseteq V(G)$, we say M $M$ is a minor of G $G$ rooted at X $X$, if M $M$ is a minor of G $G$ such that each bag of M $M$ contains at most one vertex of X $X$ and X $X$ is a subset of the union of all bags. We show that G $G$ has a highly connected minor rooted at X $X$ if X ⊆ V( G ) $X\subseteq V(G)$ cannot be separated in G $G$ by removing a few vertices of G $G$. Combining these investigations and the theory of Tutte paths in the planar case yields locally spanning versions of six well‐known results about degree‐bounded trees, Hamiltonian paths and cycles, and 2‐connected subgraphs of graphs.
Wiley Online Library
以上显示的是最相近的搜索结果。 查看全部搜索结果

Google学术搜索按钮

example.edu/paper.pdf
搜索
获取 PDF 文件
引用
References