scientific article; zbMATH DE number 4095507
From MaRDI portal
Publication:3822196
[For the entire collection see Zbl 0665.00002.] An edge e of a k-connected graph G is said to be k-contractible if the graph obtained from G by contracting e is k-connected. It is known that every triangle-free k-connected graph G contains a k-contractible edge (Thomassen), and these edges induce a 2-connected spanning subgraph of G (Dean). In this paper we show that this stronger conclusion also holds when we allow every edge to lie in at most \(\lceil k/2\rceil +1\) triangles and the minimum degree is not k. Furthermore, this result is best possible.
Recommendations
- Contractible edges in triangle-free graphs
- Contractible edges in non-separating cycles
- Contractible edges and triangles in k-connected graphs
- Contractible edges in \(k\)-connected graphs with minimum degree greater than or equal to \(\lfloor \frac{ 3 k - 1}{ 2} \rfloor \)
- scientific article; zbMATH DE number 4160775
Cited in
(5)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3822196)