Abstract
We consider graphs, which are finite, undirected, without loops and in which multiple edges are possible. For each natural numberk letg(k) be the smallest natural numbern, so that the following holds:
LetG be ann-edge-connected graph and lets 1,...,s k,t 1,...,t k be vertices ofG. Then for everyi ∈ {1,..., k} there existsa pathP i froms i tot i, so thatP 1,...,P k are pairwise edge-disjoint. We prove\(g\left( k \right) \leqslant \left\{ {\begin{array}{*{20}c} {k + 1, if k is odd} \\ {k + 2, if k is even} \\ \end{array} } \right.\)
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Mader, W.: Eine Reduktionsmethode für den Kantenzusammenhang in Graphen Math. Nachr.93, 187–204 (1979)
Okamura, H.: Multicommodity Flows in Graphs II. Japan. J. Math.10, 99–116 (1984)
Okamura, H.: Paths and Edge-Connectivity in Graphs. J. Comb. Theory (B)37, 151–172 (1984)
Okamura, H.: Paths ink-Edge-Connected Graphs. J. Comb. Theory (B)45, 345–355 (1988)
Okamura, H.: Every 4k-Edge-Connected Graph is weakly 3k-linked. Graphs and Combinatorics6, 179–185 (1990)
Okamura, H.: Every 6k-Edge-Connected Graph is weakly 5k-linked. Preliminary version
Thomassen, C.: 2-Linked Graphs. Europ. J. Comb.1, 371–378 (1980)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Huck, A. A sufficient condition for graphs to be weaklyk-linked. Graphs and Combinatorics 7, 323–351 (1991). https://doi.org/10.1007/BF01787639
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01787639