Edge-connectivity and edge-disjoint spanning trees (Q1011773): Difference between revisions

For a subset \(X\) of edges of a graph \(G\), \(\omega(G-X)\) denotes the number of components of the subgraph \(G-X\). For an integer \(c\) such that \(2\leq c\leq|V(G)|\) the \textit{higher order of edge-connectivity}, \(\lambda_c(G)\), and the \textit{higher order of edge-toughness}, \(\tau_{c-1}(G)\), are defined by \(\lambda_c(G)=\min\{|X|\}\), \(\tau_{c-1}(G)=\min\frac{|X|}{\omega(G-X)-c}\), where the minima are taken over all subsets \(X\subseteq E(G)\) such that \(\omega(G-X)\geq c\) [\textit{C. C. Chen, K. M. Koh} and \textit{Y. H. Peng}, ``On the higher-order edge toughness of a graph'', Discrete Math. 111, No. 1--3, 113--123 (1993; Zbl 0789.05086)]. From the authors' introduction and abstract: ``Over ten years ago Catlin left an unpublished note proving a theorem which characterizes the edge-connectivity of a connected graph \(G\) in terms of the spanning tree packing numbers of its subgraphs. \dots Sadly the author passed away on April 20, 1995. \dots In this paper we establish a relationship between \(\lambda_c(G)\) and \(\tau_{c-1}(G)\) which gives a characterization of the edge-connectivity of a graph \(G\) in terms of the spanning tree packing number of subgraphs of \(G\). The digraph analogue is also obtained. The main results are applied to show that, if a graph \(G\) is \(s\)-hamiltonian, then \(L(G)\) is also \(s\)-hamiltonian, and that, if a graph \(G\) is \(s\)-hamiltonian-connected, then \(L(G)\) is also \(s\)-hamiltonian-connected.''