Every 4k-edge-connected graph is weakly 3k-linked

DOI10.1007/BF01787729MaRDI QIDQ920108zbMATH OpenFDO

Authors Haruko Okamura

Publication date 1990

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01787729

zbMATH Keywords

weakly k-linked

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40)

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)\).

Recommendations

• Every line graph of a 4-edge-connected graph is \(\mathbf Z_3\)-connected
• A sufficient condition for graphs to be weakly \(k\)-linked
• A sufficient condition for a graph to be weakly k-linked
• A characterization of weakly four‐connected graphs
• The 3-connected graphs with exactly \(k\) non-essential edges
• Weakly 3-Connected Graphs
• Minimally 4-edge\(^ \#\)-connected graphs
• The \(k\)-critical \(2k\)-connected graphs for \(k\in\{3,4\}\)
• scientific article; zbMATH DE number 1530019
• A bound on 4-restricted edge connectivity of graphs

Cites work

• 2-linked graphs
• A Reduction Method for Edge-Connectivity in Graphs
• A sufficient condition for a graph to be weakly k-linked
• scientific article; zbMATH DE number 3947966 (Why is no real title available?)
• Paths and edge-connectivity in graphs
• Paths and edge-connectivity in graphs. III: Six-terminal k paths
• Paths in graphs, reducing the edge-connectivity only by two

Cited in

(5)

• A sufficient condition for graphs to be weakly \(k\)-linked
• On Sufficient Degree Conditions for a Graph to be k-linked
• Liftings in finite graphs and linkages in infinite graphs with prescribed edge-connectivity
• Paths containing two adjacent edges in \((2k+1)\)-edge-connected graphs
• A sufficient condition for a graph to be weakly k-linked

This page was built for publication: Every 4k-edge-connected graph is weakly 3k-linked

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q920108)