Connectivity keeping caterpillars and spiders in 2-connected graphs
Let \(V(G)\) denote the vertex set of a graph \(G\). And for a subset \(X\subset V\), let \(G-X\) denote the subgraph of \(G\) obtained by deleting the elements in \(X\) from \(G\). Further suppose that \(\delta(G)\) denotes the minimum degree of \(G\). \textit{G. Chartrand} et al. [Proc. Am. Math. Soc. 32, 63--68 (1972; Zbl 0228.05118)] proved the following. Theorem. Every \(k\)-connected graph \(G\) with minimum degree \(\delta(G)\ge \lfloor{3k/2}\rfloor\) has a vertex \(x\) such that \(G-x\) remains \(k\)-connected. In a similar vein, \textit{W. Mader} [J. Graph Theory 65, No. 1, 61--69 (2010; Zbl 1234.05145)] conjectured the following. [Conjectures 1 and 2] For every tree \(T\) with \(n\) vertices, every \(k\)-connected graph \(G\) with \(\delta(G)\ge \lfloor{3k/2} + n-1\) contains a subtree \(T^\prime\) isomorphic to \(T\) such that \(G-V(T^\prime)\) remains \(k\)-connected. Towards this conjecture, \textit{W. Mader} [ibid. 69, No. 3--4, 324--329 (2012; Zbl 1242.05147)] proved the following. Theorem. Let \(T\) be a tree with \(n\) vertices and let \(G\) be a \(k\)-connected graph with \(\delta(G)\ge 2(k-1+n)^2+n-1\), for positive integers \(k,n\). Then there is a tree \(T^\prime\subseteq G\) isomorphic to \(T\) such that \(G-V(T^\prime)\) remains \(k\)-connected. The current paper proved Mader's conjecture for \(k=2\) and two particular types of trees, the so called caterpillars (trees in which a single path is incident to every edge) and spiders (trees with at most one vertex with degree more than two). That is, they proved the following. Theorems 7 and 10. For every caterpillar or spider \(T\) with \(n\) vertices, every 2-connected graph \(G\) with \(\delta(G)\ge n +2\) contains a subtree \(T^\prime\subseteq G\) isomorphic to \(T\) such that \(G-V(T^\prime)\) remains 2-connected.
- Connectivity keeping trees in 2-connected graphs with girth conditions
- Connectivity keeping trees in 2-connected graphs
- Non-separating trees in connected graphs
- Connectivity keeping trees in 2-connected graphs
- Minimal \(k\)-connected graphs with minimal number of vertices of degree \(k\)
- Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions
- Connectivity preserving trees in k‐connected or k‐edge‐connected graphs
- Connectivity keeping edges in graphs with large minimum degree
- Connectivity keeping stars or double-stars in 2-connected graphs
- Connectivity keeping trees in 3-connected or 3-edge-connected graphs
- Connectivity keeping edges in graphs with large minimum degree
- Connectivity keeping paths in k-connected graphs
- Connectivity keeping stars or double-stars in 2-connected graphs
- Connectivity keeping trees in 2-connected graphs
- Connectivity keeping trees in k-connected graphs
- Critically n-Connected Graphs
- Graph theory
- Non-separating trees in connected graphs
- Nonseparating trees in 2-connected graphs and oriented trees in strongly connected digraphs
- Graphs with only caterpillars as spanning trees
- Nonseparating trees in 2-connected graphs and oriented trees in strongly connected digraphs
- Connectivity keeping stars or double-stars in 2-connected graphs
- Connectivity keeping trees in 2-connected graphs with girth conditions
- Connectivity keeping paths in \(k\)-connected bipartite graphs
- Connectivity keeping caterpillars and spiders in bipartite graphs with connectivity at most three
- Connectivity keeping paths in k-connected graphs
- Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions
- Connectivity keeping trees in 2-connected graphs
- Connectivity preserving trees in k‐connected or k‐edge‐connected graphs
- Mader's conjecture for graphs with small connectivity
- Connectivity keeping edges of trees in 3-connected or 3-edge-connected graphs
- Highly connected triples and Mader's conjecture
- Non-path results on the connectivity keeping problem
- A survey on the vertex-(edge-)k-maximal graphs and the k-vertex-(edge-)connected graphs with redundant subgraphs
- Proof of a conjecture on connectivity keeping odd paths in k-connected bipartite graphs
- Connectivity keeping paths for k-connected bipartite graphs
- Exploring redundant trees in bipartite graphs
This page was built for publication: Connectivity keeping caterpillars and spiders in 2-connected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2222940)
