Paths and edge-connectivity in graphs. III: Six-terminal k paths
type: Item
instance of: scholarly article
title: Paths and edge-connectivity in graphs. III: Six-terminal k paths
zbMATH Open document ID: 0643.05047
DOI: 10.1007/BF01788539
author: Haruko Okamura
published in: Graphs and Combinatorics
publication date: 1987-01-01T00:00:00Z
review text: [For part II see the author's paper in Number Theory and Combinatorics, Proc. Conf. Tokyo/Jap., Okayama/Jap. and Kyoto/Jap. 1984, 337-352 (1985; Zbl 0613.05036).] As in part I [J. Comb. Theory, Ser. B 37, 151-172 (1984; Zbl 0548.05039)], the author studies the existence in graphs of edge-disjoint paths which have given ends. Let \(k\geq 1\) be an odd integer and \((s_ i,t_ i)\), \(1\leq i\leq k\), be pairs of vertices of a graph G. The author proves that if the number of considered vertices \(s_ 1,...,s_ k,t_ 1,...,t_ k\) is at most 6 and if the maximal number of edge-disjoint paths between each given pair of vertices \((s_ i,t_ i)\) (1\(\leq i\leq k)\) is at least k, then there exist k disjoint paths \(P_ 1,...,P_ k\) such that \(P_ i\) is a path between \(s_ i\) and \(t_ i\) (1\(\leq i\leq k)\).
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4047769
zbMATH Keywords: connectivity
zbMATH Keywords: edge-disjoint paths
zbMATH Keywords: ends
MaRDI profile type: Publication
cites work: A sufficient condition for a graph to be weakly k-linked
cites work: A Reduction Method for Edge-Connectivity in Graphs
cites work: Q3718456
cites work: Paths and edge-connectivity in graphs
cites work: Disjoint paths in graphs
cites work: 2-linked graphs
description: scientific article; zbMATH DE number 4047769