Abstract
We prove:
-
(i)
Fork ≥ 2 andα = 0, 1, every (4k + 2α)-edge-connected graph is weakly (3k + 2α)-linked.
-
(ii)
IfG is ak-edge-connected graph (k ≥ 2),s, t are vertices andf is an edge, then there exists a pathP betweens andt such thatf ∉ E(P) andG − E(P) − f is (k − 2)-edge-connected, whereE(P) denotes the edge set ofP.
Similar content being viewed by others
References
Hirata, T., Kubota, K., Saito, O.: A sufficient condition for a graph to be weaklyk-linked. J. Comb. Theory (B)36, 85–94 (1984)
Mader, W.: A reduction method for edge-connectivity in graphs. Ann. Discrete Math.3, 145–164 (1978)
Mader, W.: Paths in graphs, reducing the edge-connectivity only by two. Graphs and Combinatorics1, 81–89 (1985)
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 and edge-connectivity in graphs II. In: Number theory and Combinatorics (Tokyo, Okayama, Kyoto 1984), pp. 337–352. Singapore: World Sci. Publishing 1985
Okamura, H.: Paths and edge-connectivity in graphs III. Six-terminalk paths. Graphs and Combinatorics3, 159–189 (1987)
Okamura, H.: Paths ink-edge-connected graphs. J. Comb. Theory (B)45, 345–355 (1988)
Thomassen, C.: 2-linked graphs. European J. Comb.1, 371–378 (1980)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Okamura, H. Every 4k-edge-connected graph is Weakly 3k-linked. Graphs and Combinatorics 6, 179–185 (1990). https://doi.org/10.1007/BF01787729
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01787729