Edge-connectivity and edge-disjoint spanning trees.

*(English)*Zbl 1168.05039For 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.”

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
PDF
BibTeX
XML
Cite

\textit{P. A. Catlin} et al., Discrete Math. 309, No. 5, 1033--1040 (2009; Zbl 1168.05039)

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.