Connectivity keeping caterpillars and spiders in 2-connected graphs (Q2222940): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 07:21, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Connectivity keeping caterpillars and spiders in 2-connected graphs |
scientific article |
Statements
Connectivity keeping caterpillars and spiders in 2-connected graphs (English)
0 references
27 January 2021
0 references
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.
0 references
caterpillars
0 references
spider
0 references
2-connected graphs
0 references
connectivity
0 references
trees
0 references