Toughness of K_a,t-minor-free graphs
Summary: The toughness of a non-complete graph \(G\) is the minimum value of \(\frac{|S|}{\omega(G-S)}\) among all separating vertex sets \(S \subset V (G)\), where \(\omega (G - S)\geqslant 2\) is the number of components of \(G - S\). It is well-known that every 3-connected planar graph has toughness greater than 1/2. Related to this property, every 3-connected planar graph has many good substructures, such as a spanning tree with maximum degree three, a 2-walk, etc. Realizing that 3-connected planar graphs are essentially the same as 3-connected \(K_{3,3}\)-minor-free graphs, we consider a generalization to \(a\)-connected \(K_{a,t}\)-minor-free graphs, where \(3\leqslant a\leqslant t\). We prove that there exists a positive constant \(h(a, t)\) such that every \(a\)-connected \(K_{a,t}\)-minor-free graph \(G\) has toughness at least \(h(a, t)\). For the case where \(a = 3\) and \(t\) is odd, we obtain the best possible value for \(h(3, t)\). As a corollary it is proved that every such graph of order \(n\) contains a cycle of length \(\Omega (\log _{h(a,t)} n)\).
- Toughness and spanning trees in K4‐minor‐free graphs
- The circumference of a graph with no \(K_{3,t}\)-minor
- On a connection between the existence of k-trees and the toughness of a graph
- Toughness threshold for the existence of 2-walks in \(K_{4}\)-minor-free graphs
- Maximum and minimum toughness of graphs of small genus
- Maximum and minimum toughness of graphs of small genus
- Labeled \(K_{2,t}\) minors in plane graphs
- The circumference of a graph with no \(K_{3,t}\)-minor. II
- Properties of minimally \(t\)-tough graphs
- Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey
- A characterization of \(K_{2,4}\)-minor-free graphs
- Spanning trees in 3-connected \(K_{3,t}\)-minor-free graphs
- Toughness and spanning trees in K4‐minor‐free graphs
- Spanning trees: A survey
- Spanning trees in 3-connected \(K_{3,t}\)-minor-free graphs
- Uniform polynomial kernel for deletion to \(K_{2,p}\) minor-free graphs
- Toughness threshold for the existence of 2-walks in \(K_{4}\)-minor-free graphs
This page was built for publication: Toughness of \(K_{a,t}\)-minor-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q554002)
