Edge-connectivity and edge-disjoint spanning trees. (English) Zbl 1168.05039

Catlin, Paul A.; Lai, Hong-Jian; Shao, Yehong

Discrete Math. 309, No. 5, 1033-1040 (2009).

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.”

Reviewer: William G. Brown (Montréal)

MSC:

05C40	Connectivity
05C05	Trees
05C45	Eulerian and Hamiltonian graphs
05C20	Directed graphs (digraphs), tournaments

Keywords:

edge-connectivity; spanning tree packing number; higher order of edge-connectivity; higher order of edge-toughness; \(k\)-arc-connected digraphs; spanning arborescences; line graph; \(s\)-Hamiltonian; \(s\)-Hamiltonian-connected

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