Abstract
Suppose thatk ≥ 1 is an odd integer, (s 1,t 1),..., (s k> ,t k ) are pairs of vertices of a graphG andλ(s i ,t i ) is the maximal number of edge-disjoint paths betweens i andt i . We prove that ifλ(s i ,t i )≥ k (1≤ i ≤ k) and |{s 1,...s k ,t 1,...,t k }| ≤ 6, then there exist edge-disjoint pathsP 1,...,P k such thatP i has endss i andt i (1≤ i ≤ k).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Cypher, A.: An approach to thek paths problem. In: Proceedings, 12th Annual ACM Symposium on Theory of Computing, pp. 211–217. New York: ACM 1980
Hirata, T., Kubota K., Saito, O.: A sufficient condition for a graph to be weeklyk-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)
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
Seymour, P.D.: Disjoint paths in graphs. Discrete Math.29, 293–309 (1980)
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
Okamura, H. Paths and edge-connectivity in graphs III. Six-terminalk paths. Graphs and Combinatorics 3, 159–189 (1987). https://doi.org/10.1007/BF01788539
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01788539