Every 4k-edge-connected graph is weakly 3k-linked
type: Item
instance of: scholarly article
title: Every 4k-edge-connected graph is weakly 3k-linked
zbMATH Open document ID: 0708.05036
DOI: 10.1007/BF01787729
author: Haruko Okamura
published in: Graphs and Combinatorics
publication date: 1990-01-01T00:00:00Z
review text: A graph is weakly k-linked, if for every k pairs of vertices \((s_ i,t_ i)\) there exist k edge-disjoint paths \(P_ i\) such that \(P_ i\) joins \(s_ i\) and \(t_ i\) (1\(\leq i\leq k)\). Let be g(k) the minimum of the edge connectivity numbers such that for each graph G which is g(k) edge connected holds: G is weakly k-linked. \textit{C. Thomassen} [Eur. J. Comb. 1, 371-378 (1980; Zbl 0457.05044)] conjectured that \(g(2k+1)=g(2k)=2k+1\) (k\(\geq 1)\). Here the author proves g(3k)\(\leq 4k\) and \(g(3k+1)\leq g(3k+2)\leq 4k+2\) (k\(\geq 2)\).
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4162916
zbMATH Keywords: weakly k-linked
reviewed by: Michael Hager
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: Paths in graphs, reducing the edge-connectivity only by two
cites work: Q3718456
cites work: Paths and edge-connectivity in graphs
cites work: Paths and edge-connectivity in graphs. III: Six-terminal k paths
cites work: 2-linked graphs
Recommended article: Every line graph of a 4-edge-connected graph is \(\mathbf Z_3\)-connected
Recommended article: A sufficient condition for graphs to be weakly \(k\)-linked
Recommended article: A sufficient condition for a graph to be weakly k-linked
Recommended article: A characterization of weakly four‐connected graphs
Recommended article: The 3-connected graphs with exactly \(k\) non-essential edges
Recommended article: Weakly 3-Connected Graphs
Recommended article: Minimally 4-edge\(^ \#\)-connected graphs
Recommended article: The \(k\)-critical \(2k\)-connected graphs for \(k\in\{3,4\}\)
Recommended article: Q4514553
Recommended article: A bound on 4-restricted edge connectivity of graphs
description: scientific article; zbMATH DE number 4162916