×

zbMATH — the first resource for mathematics

Edge-connectivity and edge-disjoint spanning trees. (English) Zbl 1168.05039
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 higher order of edge-connectivity, \(\lambda_c(G)\), and the 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\) [C. C. Chen, K. M. Koh and 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. …Sadly the author passed away on April 20, 1995. …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.”

MSC:
05C40 Connectivity
05C05 Trees
05C45 Eulerian and Hamiltonian graphs
05C20 Directed graphs (digraphs), tournaments
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bondy, A.J.; Murty, U.S.R., Graph theory with applications, (1976), American Elsevier New York · Zbl 1226.05083
[2] P.A. Catlin, Edge-connectivity and edge-disjoint spanning trees. See: http://www.math.wvu.edu/ hjlai/Pdf/Catlin_Pdf/Catlin49a.pdf preprint · Zbl 1168.05039
[3] Catlin, P.A.; Lai, H.-J., Spanning trails joining two given edges, (), 207-222 · Zbl 0841.05067
[4] Catlin, P.A.; Grossman, J.W.; Hobbs, A.M.; Lai, H.-J., Fractional arboricity, strength, and principal partitions in graphs and matroids, Discrete appl. math., 40, 285-302, (1992) · Zbl 0773.05033
[5] Chen, C.C.; Koh, K.M.; Peng, Y.H., On the higher order of edge-toughness of a graph, Discrete math., 111, 113-123, (1993) · Zbl 0789.05086
[6] Chen, Z.H.; Lai, H.-J., The higher-order edge toughness of a graph and truncated uniformly dense matroids, J. combin. math. combin. computing, 22, 157-160, (1996) · Zbl 0863.05046
[7] J. Edmonds, Edge-disjoint branchings, in: R. Rustin (Ed.), Combinatorial Algorithms, Academic Press, New York, pp. 91-96
[8] Lesniak-Foster, L., On \(n\)-hamiltonion line graphs, J. combin. theory ser. B, 22, 263-273, (1977) · Zbl 0307.05122
[9] Nash-Williams, C.St.J.A., On orientations, connectivity and odd-vertex pairings in finite graphs, Canad. J. math., 12, 555-567, (1960) · Zbl 0096.38002
[10] Harary, F.; Nash-Williams, C.St.J.A., On eulerian and Hamiltonian graphs and line graphs, Canad. math. bull., 8, 701-709, (1965) · Zbl 0136.44704
[11] Zhan, S., Hamiltonian connectedness of line graphs, Ars combin., 22, 89-95, (1986) · Zbl 0611.05038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.